Search Results

1 - 10 of 10 items :

Clear All

Summary

In this paper we give a formal definition of the notion of nominative data with simple names and complex values [, , ] and formal definitions of the basic operations on such data, including naming, denaming and overlapping, following the work [].

The notion of nominative data plays an important role in the composition-nominative approach to program formalization [, ] which is a development of composition programming []. Both approaches are compared in [].

The composition-nominative approach considers mathematical models of computer software and data on various levels of abstraction and generality and provides mathematical tools for reasoning about their properties. In particular, nominative data are mathematical models of data which are stored and processed in computer systems. The composition-nominative approach considers different types [, ] of nominative data, but all of them are based on the name-value relation. One powerful type of nominative data, which is suitable for representing many kinds of data commonly used in programming like lists, multidimensional arrays, trees, tables, etc. is the type of nominative data with simple (abstract) names and complex (structured) values. The set of nominative data of given type together with a number of basic operations on them like naming, denaming and overlapping [] form an algebra which is called data algebra.

In the composition-nominative approach computer programs which process data are modeled as partial functions which map nominative data from the carrier of a given data algebra (input data) to nominative data (output data). Such functions are also called binominative functions. Programs which evaluate conditions are modeled as partial predicates on nominative data (nominative predicates). Programming language constructs like sequential execution, branching, cycle, etc. which construct programs from the existing programs are modeled as operations which take binominative functions and predicates and produce binominative functions. Such operations are called compositions. A set of binominative functions and a set of predicates together with appropriate compositions form an algebra which is called program algebra. This algebra serves as a semantic model of a programming language.

For functions over nominative data a special computability called abstract computability is introduces and complete classes of computable functions are specified [].

For reasoning about properties of programs modeled as binominative functions a Floyd-Hoare style logic [, ] is introduced and applied [, , , , , ]. One advantage of this approach to reasoning about programs is that it naturally handles programs which process complex data structures (which can be quite straightforwardly represented as nominative data). Also, unlike classical Floyd-Hoare logic, the mentioned logic allows reasoning about assertions which include partial pre- and post-conditions [].

Besides modeling data processed by programs, nominative data can be also applied to modeling data processed by signal processing systems in the context of the mathematical systems theory [, , , , ].

Summary

We show that the set of all partial predicates over a set D together with the disjunction, conjunction, and negation operations, defined in accordance with the truth tables of S.C. Kleene’s strong logic of indeterminacy [], forms a Kleene algebra. A Kleene algebra is a De Morgan algebra [] (also called quasi-Boolean algebra) which satisfies the condition x¬:xy¬ :y (sometimes called the normality axiom). We use the formalization of De Morgan algebras from [].

The term “Kleene algebra” was introduced by A. Monteiro and D. Brignole in []. A similar notion of a “normal i-lattice” had been previously studied by J.A. Kalman []. More details about the origin of this notion and its relation to other notions can be found in [, , , ]. It should be noted that there is a different widely known class of algebras, also called Kleene algebras [, ], which generalize the algebra of regular expressions, however, the term “Kleene algebra” used in this paper does not refer to them.

Algebras of partial predicates naturally arise in computability theory in the study on partial recursive predicates. They were studied in connection with non-classical logics [, , , , , ]. A partial predicate also corresponds to the notion of a partial set [] on a given domain, which represents a (partial) property which for any given element of this domain may hold, not hold, or neither hold nor not hold. The field of all partial sets on a given domain is an algebra with generalized operations of union, intersection, complement, and three constants (0, 1, n which is the fixed point of complement) which can be generalized to an equational class of algebras called DMF-algebras (De Morgan algebras with a single fixed point of involution) []. In [] partial sets and DMF-algebras were considered as a basis for unification of set-theoretic and linguistic approaches to probability.

Partial predicates over classes of mathematical models of data were used for formalizing semantics of computer programs in the composition-nominative approach to program formalization [, , , ], for formalizing extensions of the Floyd-Hoare logic [, ] which allow reasoning about properties of programs in the case of partial pre- and postconditions [, , , ], for formalizing dynamical models with partial behaviors in the context of the mathematical systems theory [, , , , ].

Summary

This paper continues formalization in Mizar , ] of basic notions of the composition-nominative approach to program semantics which was started in , .

The composition-nominative approach studies mathematical models of computer programs and data on various levels of abstraction and generality and provides tools for reasoning about their properties. Besides formalization of semantics of programs, certain elements of the composition-nominative approach were applied to abstract systems in a mathematical systems theory [, , , , ].

In the paper we introduce a definition of the notion of a binominative function over a set D understood as a partial function which maps elements of D to D. The sets of binominative functions and nominative predicates over given sets form the carrier of the generalized Glushkov algorithmic algebra . This algebra can be used to formalize algorithms which operate on various data structures (such as multidimensional arrays, lists, etc.) and reason about their properties.

We formalize the operations of this algebra (also called compositions) which are valid over uninterpretated data and which include among others the sequential composition, the prediction composition, the branching composition, the monotone Floyd-Hoare composition, and the cycle composition. The details on formalization of nominative data and the operations of the algorithmic algebra over them are described in , , .

Summary

This paper continues formalization in the Mizar system , ] of basic notions of the composition-nominative approach to program semantics which was started in , , ].

The composition-nominative approach studies mathematical models of computer programs and data on various levels of abstraction and generality and provides tools for reasoning about their properties. In particular, data in computer systems are modeled as nominative data . Besides formalization of semantics of programs, certain elements of the composition-nominative approach were applied to abstract systems in a mathematical systems theory , , , , ].

In the paper we give a formal definition of the notions of a binominative function over given sets of names and values (i.e. a partial function which maps simple-named complex-valued nominative data to such data) and a nominative predicate (a partial predicate on simple-named complex-valued nominative data). The sets of such binominative functions and nominative predicates form the carrier of the generalized Glushkov algorithmic algebra for simple-named complex-valued nominative data . This algebra can be used to formalize algorithms which operate on various data structures (such as multidimensional arrays, lists, etc.) and reason about their properties.

In particular, we formalize the operations of this algebra which require a specification of a data domain and which include the existential quantifier, the assignment composition, the composition of superposition into a predicate, the composition of superposition into a binominative function, the name checking predicate. The details on formalization of nominative data and the operations of the algorithmic algebra over them are described in [, , ].

Summary

In this paper we present a formalization in the Mizar system , ] of the correctness of the subtraction-based version of Euclid’s algorithm computing the greatest common divisor of natural numbers. The algorithm is written in terms of simple-named complex-valued nominative data , .

The validity of the algorithm is presented in terms of semantic Floyd-Hoare triples over such data . Proofs of the correctness are based on an inference system for an extended Floyd-Hoare logic with partial pre- and post-conditions , , , ].

Summary

In this paper we present a formalization in the Mizar system [3],[1] of the partial correctness of the algorithm:

i := val.1
j := val.2
n := val.3
s := val.4
while (i <> n)
      i := i + j
     s := s * i
return s

computing the factorial of given natural number n, where variables i, n, s are located as values of a V-valued Function, loc, as: loc/.1 = i, loc/.3 = n and loc/.4 = s, and the constant 1 is located in the location loc/.2 = j (set V represents simple names of considered nominative data [16]).

This work continues a formal verification of algorithms written in terms of simple-named complex-valued nominative data [6],[8],[14],[10],[11],[12]. The validity of the algorithm is presented in terms of semantic Floyd-Hoare triples over such data [9]. Proofs of the correctness are based on an inference system for an extended Floyd-Hoare logic [2],[4] with partial pre- and post-conditions [13],[15],[7],[5].

Summary

This work continues a formal verification of algorithms written in terms of simple-named complex-valued nominative data [6],[8],[15],[11],[12],[13]. In this paper we present a formalization in the Mizar system [3],[1] of the partial correctness of the algorithm:

i := val.1
j := val.2
b := val.3
n := val.4
s := val.5
while (i <> n)
    i := i + j
    s := s * b
return s

computing the natural n power of given complex number b, where variables i, b, n, s are located as values of a V-valued Function, loc, as: loc/.1 = i, loc/.3 = b, loc/.4 = n and loc/.5 = s, and the constant 1 is located in the location loc/.2 = j (set V represents simple names of considered nominative data [17]).

The validity of the algorithm is presented in terms of semantic Floyd-Hoare triples over such data [9]. Proofs of the correctness are based on an inference system for an extended Floyd-Hoare logic [2],[4] with partial pre- and post-conditions [14],[16],[7],[5].

Summary

In the article [10] a formal system for Propositional Linear Temporal Logic (in short LTLB) with normal semantics is introduced. The language of this logic consists of “until” operator in a very strict version. The very strict “until” operator enables to express all other temporal operators.

In this article we construct a formal system for LTLB with the initial semantics [12]. Initial semantics means that we define the validity of the formula in a model as satisfaction in the initial state of model while normal semantics means that we define the validity as satisfaction in all states of model. We prove the Deduction Theorem, and the soundness and completeness of the introduced formal system. We also prove some theorems to compare both formal systems, i.e., the one introduced in the article [10] and the one introduced in this article.

Formal systems for temporal logics are applied in the verification of computer programs. In order to carry out the verification one has to derive an appropriate formula within a selected formal system. The formal systems introduced in [10] and in this article can be used to carry out such verifications in Mizar [4].

Summary

In the paper we give a formalization in the Mizar system , ] of the rules of an inference system for an extended Floyd-Hoare logic with partial pre- and post-conditions which was proposed in , ]. The rules are formalized on the semantic level. The details of the approach used to implement this formalization are described in .

We formalize the notion of a semantic Floyd-Hoare triple (for an extended Floyd-Hoare logic with partial pre- and post-conditions) which is a triple of a pre-condition represented by a partial predicate, a program, represented by a partial function which maps data to data, and a post-condition, represented by a partial predicate, which informally means that if the pre-condition on a program’s input data is defined and true, and the program’s output after a run on this data is defined (a program terminates successfully), and the post-condition is defined on the program’s output, then the post-condition is true.

We formalize and prove the soundness of the rules of the inference system , ] for such semantic Floyd-Hoare triples. For reasoning about sequential composition of programs and while loops we use the rules proposed in .

The formalized rules can be used for reasoning about sequential programs, and in particular, for sequential programs on nominative data . Application of these rules often requires reasoning about partial predicates representing preand post-conditions which can be done using the formalized results on the Kleene algebra of partial predicates given in .

greatest shape factors at vertical orientation were observed in G2, G3, G8 and G14 genotypes. Table 5 Shape parameters of cornelian cherry fruits at horizontal and vertical orientations Types Shape factor Elongation Coating ratio (%) Horizontal (SF h ) Vertical (SF v ) Horizontal (E h ) Vertical (E v ) Horizontal (CR h ) Vertical (CR v ) G1 0.850 ± 0.013 ab 0.865 ± 0.041 abc 1.28 ± 0.09 h 1.05 ± 0.03 b 78.63 ± 5.01 a 94.6 ± 2.4 a G2 0.832 ± 0.024 abcd 0.882 ± 0.019 ab 1.43 ± 0.07 cd 1.06 ± 0.03 b 70.65 ± 3.57 defg 93.6 ± 2.7 ab G3 0.851 ± 0.014 a 0.881 ± 0.010 ab 1