Search

International audience; We are interested in a natural generalization of term-rewriting techniques to what we call drags, viz. finite, directed, ordered, rooted multigraphs, each vertex of which is labeled by a function symbol. To this end, we develop a rich algebra of drags that generalizes the familiar term algebra and its associated rewriting capabilities. Viewing graphs as terms provides an initial building block for rewriting with such graphs, one that should impact the many areas where computations take place on graphs.

We define nominal equational problems of the form $$\exists \overline{W} \forall \overline{Y} : P$$ ∃ W ¯ ∀ Y ¯ : P , where $$P$$ P consists of conjunctions and disjunctions of equations $$s\approx _\alpha t$$ s ≈ α t , freshness constraints $$a\#t$$ a # t and their negations: $$s \not \approx _\alpha t$$ s ≉ α t and "Equation missing", where $$a$$ a is an atom and $$s, t$$ s , t nominal terms. We give a general definition of solution and a set of simplification rules to compute solutions in the nominal ground term algebra. For the latter, we define notions of solved form from which solutions can be easily extracted and show that the simplification rules are sound, preserving, and complete. With a particular strategy for rule application, the simplification process terminates and thus specifies an algorithm to solve nominal equational problems. These results generalise previous results obtained by Comon and Lescanne for first-order languages to languages with binding operators. In particular, we show that the problem of deciding the validity of a first-order equational formula in a language with binding operators (i.e., validity modulo $$\alpha $$ α -equality) is decidable.

We introduce a term algebra as a new formal specification language for the coordinating architectures of distributed systems consisting of a finite yet unbounded number of components. The language allows to describe infinite sets of systems whose coordination between components share the same pattern, using inductive definitions similar to the ones used to describe algebraic data types or recursive data structures. Further, we give a verification method for the parametric systems described in this language, relying on the automatic synthesis of structural invariants that enable proving general safety properties (absence of deadlocks and critical section violations). The invariants are defined using the \(\mathsf {WS}{\kappa }\mathsf {S}\) fragment of the monadic second order logic, known to be decidable by a classical automata-logic connection. This reduces the safety verification problem to checking satisfiability of a \(\mathsf {WS}{\kappa }\mathsf {S}\) formula. We implemented the invariant synthesis method into a prototype tool and carried out verification experiments on a number of non-trivial models specified using the term algebra.

A general overview of the existing difference ring theory for symbolic summation is given. Special emphasis is put on the user interface: the translation and back translation of the corresponding representations within the term algebra and the formal difference ring setting. In particular, canonical (unique) representations and their refinements in the introduced term algebra are explored by utilizing the available difference ring theory. Based on that, precise input-output specifications of the available tools of the summation package Sigma are provided.

An alpha-automaton (for alpha some ordinal) is an automaton similar to a Muller automaton that processes words of length alpha. A structure is called alpha-automatic if it can be presented by alpha-automata (completely analogous to the notion of automatic structures which can be presented by the well-known finite automata). We call a structure ordinal-automatic if it is alpha-automatic for some ordinal alpha. We continue the study of ordinal-automatic structures initiated by Schlicht and Stephan as well as by Finkel and Todorcevic. We develop a pumping lemma for alpha-automata (processing finite alpha-words, i.e., words of length alpha that have one fixed letter at all but finitely many positions). Using this pumping, we provide counterparts for the class of ordinal-automatic structures to several results on automatic structures: Every finite word alpha-automatic structure has an injective finite word alpha-automatic presentation for all alpha < omega(1) + omega(omega). This bound is sharp. We classify completely the finite word omega(n)-automatic Boolean algebras. Moreover, we show that the countable atomless Boolean algebra does not have an injective finite-word ordinal-automatic presentation. We separate the class of finite-word ordinal-automatic structures from that of tree-automatic structures by showing that free term algebras with at least 2 generators (and one binary function) are not ordinal-automatic while the free term algebra with countable infinitely many generators is known to be tree-automatic. For every ordinal alpha < omega(1) + omega(omega), we provide a sharp bound on the height of the finite word alpha-automatic well-founded order forests. For every ordinal alpha < omega(1)+ omega(omega), we provide a structure (sic)(alpha) that is complete for the class of finite-word alpha-automatic structures with respect to first-order interpretations. As a byproduct, we also lift Schlicht and Stephans's characterisation of the injectively finite-word alpha-automatic ordinals to the noninjective setting.

International audience; This paper presents an efficient implementation of geometric algebra, based on a recursive representation of the algebra elements using binary trees. The proposed approach consists in restructuring a state of the art recursive algorithm to handle parallel optimizations. The resulting algorithm is described for the outer product and the geometric product. The proposed implementation is usable for any dimensions, including high dimension (e.g. algebra of dimension 15). The method is compared with the main state of the art geometric algebra implementations , with a time complexity study as well as a practical benchmark. The tests show that our implementation is at least as fast as the main geometric algebra implementations.

This paper gives a survey on the categorical term construction based on the free algebra algorithm. In the framework of monoidal biclosed and cocomplete categories a possible concept of signature for finitary theories is introduced. Applications of these constructions are given in Goguen's category and in the category of complete lattices and join preserving maps.

Feature Algebra was introduced as an abstract framework for feature-oriented software development. One goal is to provide a common, clearly defined basis for the key ideas of feature-orientation. The algebra captures major aspects of feature-orientation, such as the hierarchical structure of features and feature composition. However, as we will show, it is not able to model aspects at the level of code, i.e., situations where code fragments of different features have to be merged. In other words, it does not reflect details of concrete implementations. In this paper we first present concrete models for the original axioms of Feature Algebra which represent the main concepts of feature-oriented programs. This shows that the abstract Feature Algebra can be interpreted in different ways. We then use these models to show that the axioms of Feature Algebra do not properly reflect all aspects of feature-orientation from the level of directory structures down to the level of actual code. This gives motivation to extend the abstract algebra, which is the second main contribution of the paper. We modify the axioms and introduce the concept of an Extended Feature Algebra. As third contribution, we introduce more operators to cover concepts like overriding in the abstract setting.

In this paper, we exhibit a relation algebra reduct of any diagonal-free cylindric algebra of dimension 3 having sufficiently strong projection and equality parameters. We also offer a complete (and corrected) proof that full first-order logic can be formalized in the calculus of binary relations (a result due to Maddux and Tarski). Finally, we use these constructions to recursively define a translation function from the sentences of first-order logic to the equational theory of Df3, which preserves validity.

In this work we present a novel formalization of universal algebra in Agda. We show that heterogeneous signatures can be elegantly modelled in type-theory using sets indexed by arities to represent operations. We prove elementary results of heterogeneous algebras, including the proof that the term algebra is initial and the proofs of the three isomorphism theorems. We further formalize equational theory and prove soundness and completeness. At the end, we define (derived) signature morphisms, from which we get the contravariant functor between algebras; moreover, we also proved that, under some restrictions, the translation of a theory induces a contra-variant functor between models. Fil: Gunther, Emmanuel. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía y Física; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Gadea, Alejandro Emilio. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía y Física; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Pagano, Miguel Maria. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía y Física; Argentina

From a declarative variant of Remy's algorithm for uniform random generation of binary trees, we derive a generalization to term algebras of an arbitrary signature. With trees seen as sets of edges connecting vertices labeled with logic variables, we use Prolog's multiple-answer generation mechanism to derive a generic algorithm that counts terms of a given size, generates them all, or samples a random term given the signature of a term algebra. As applications, we implement generators for term algebras defining Motzkin trees, use all-term and random-term generation for mutual cross-testing and describe an extension mechanism that transforms a random sampler for Motzkin trees into one for closed lambda terms.

We introduce a concept of graph algebra that generalizes the traditional concept of algebra in the sense that (1) we use graphs rather than sets as carriers, and (2) we generalize algebraic operations to diagrammatic operations over graphs, which we call graph operations.

We present a general framework for balancing expressions (terms) in the form of so-called tree straight-line programs. The latter can be seen as circuits over the free term algebra extended by contexts (terms with a hole) and the operations, which insert terms/contexts into contexts. In Ref. [16], it was shown that one can compute for a given term of size n in logspace a tree straight-line program of depth O (log n ) and size O ( n / log n ). In the present article, it is shown that the conversion can be done in DLOGTIME-uniform TC 0 . This allows reducing the term evaluation problem over an arbitrary algebra A to the term evaluation problem over a derived two-sorted algebra F ( A ). Three applications are presented: (i) an alternative proof for a recent result by Krebs et al. [25] on the expression evaluation problem is given; (ii) it is shown that expressions for an arbitrary (possibly non-commutative) semiring can be transformed in DLOGTIME-uniform TC 0 into equivalent circuits of logarithmic depth and size O ( n / log n ); and, (iii) a corresponding result for regular expressions is shown.

In terms of algebra, the context-free and E0L grammatical derivations are traditionally defined over the free monoids generated by total alphabets of these grammars under the operation of concatenation. The present chapter, however, introduces and investigates these derivations over different algebraic structures in order to increase the generative power of these grammars.

In 2003 we showed that right-linear systems of equations over regular expressions, when interpreted in a category of trees, have a solution whenever they enjoy a specific property that we called hierarchicity and that is instrumental to avoid critical mutual recursive definitions. In this note, we prove that a right-linear system of polynomial endofunctors on a cocartesian monoidal closed category which enjoys parameterized left list arithmeticity, has an initial algebra, provided it satisfies a property similar to hierarchicity.

Traditionally, from an algebraic viewpoint, automata work over free monoids. The present chapter, however, modifies this standard approach so they work over other algebraic structures. More specifically, this chapter discusses a modification of pushdown automata that is based on two-sided pushdowns into which symbols are pushed from both ends.

Algebras of imperative programming languages have been successful in reasoning about programs. In general an algebra of programs is an algebraic structure with programs as elements and with program compositions (sequential composition, choice, skip) as algebra operations. Various versions of these algebras were introduced to model partial correctness, total correctness, refinement, demonic choice, and other aspects. We introduce here an algebra which can be used to model total correctness, refinement, demonic and angelic choice. The basic model of our algebra are monotonic Boolean transformers (monotonic functions from a Boolean algebra to itself).

Summary We introduce algorithmic logic - an algebraic approach according to [25]. It is done in three stages: propositional calculus, quantifier calculus with equality, and finally proper algorithmic logic. For each stage appropriate signature and theory are defined. Propositional calculus and quantifier calculus with equality are explored according to [24]. A language is introduced with language signature including free variables, substitution, and equality. Algorithmic logic requires a bialgebra structure which is an extension of language signature and program algebra. While-if algebra of generator set and algebraic signature is bialgebra with appropriate properties and is used as basic type of algebraic logic.

Process algebra is an algebra method of concurrency theory. Based on the relevant theories of process algebra, it is set forth several class process algebras and the important role they played in the development history of research on process algebra according to two breakthrough of process algebra. Finally it is introduced the applications of algebra process in the protocol verification, workflow description and other areas.

In this paper, we first introduce the notion of implication filters in BL-algebras and then state and prove some theorems which determine the relationships of these filters and other filters in BL-algebras. We also introduce the notion of implication BL-algebras and investigate its properties, as well as the relationship of implication BL-algebras and other algebraic structures.

We propose an algebra of languages and transformations as a means of compositional syntactic language extension. The algebra provides a layer of high-level abstractions built on top of languages (captured by context-free grammars) and transformations (captured by constructive catamorphisms). The algebra is self-contained in that any term of the algebra specifying a transformation can be reduced to a constant catamorphism, before the transformation is run. Thus, the algebra comes ''for free'' without sacrificing the strong safety and efficiency properties of constructive catamorphisms. The entire algebra as presented in the paper is implemented as the Banana Algebra Tool which may be used to syntactically extend languages in an incremental and modular fashion via algebraic composition of previously defined languages and transformations. We demonstrate and evaluate the tool via several kinds of extensions.

Summary We introduce an algebra with free variables, an algebra with undefined values, a program algebra over a term algebra, an algebra with integers, and an algebra with arrays. Program algebra is defined as universal algebra with assignments. Programs depend on the set of generators with supporting variables and supporting terms which determine the value of free variables in the next state. The execution of a program is changing state according to successor function using supporting terms.

This paper brings together Dana Scottʼs measure-based semantics for the propositional modal logic S4, and recent work in Dynamic Topological Logic. In a series of recent talks, Scott showed that the language of S4 can be interpreted in the Lebesgue measure algebra, M , or algebra of Borel subsets of the real interval, [ 0 , 1 ] , modulo sets of measure zero. Conjunctions, disjunctions and negations are interpreted via the Boolean structure of the algebra, and we add an interior operator on M that interprets the □-modality. In this paper we show how to extend this measure-based semantics to the bimodal logic S 4 C . S 4 C is interpreted in ‘dynamic topological systems,’ or topological spaces together with a continuous function acting on the space. We extend Scottʼs measure based semantics to this bimodal logic by defining a class of operators on the algebra M , which we call O-operators and which take the place of continuous functions in the topological semantics for S 4 C . The main result of the paper is that S 4 C is complete for the Lebesgue measure algebra. A strengthening of this result, also proved here, is that there is a single measure-based model in which all non-theorems of S 4 C are refuted.

The mathematical basics of the non-classical approach to the logical synthesis of k-valued digital structures based on the replacement of the classic mathematical apparatus of logic synthesis (Boolean algebra) to the proposed mathematical apparatus — linear algebra are considered. The logic synthesis process of two valued and multi-valued digital structures in linear algebra including the formation of bases of a linear space and original representation of the implemented logical function are discussed. Mathematical advantages of the proposed approach, which could be the basis for designing of high-speed digital logic structures for various applications are considered.

We extend the relational algebra of Chin and Tarski so that it is multisorted or, as we prefer, typed. Each type supports a local Boolean algebra outfitted with a converse operator. From Lyndon, we know that relation algebras cannot be represented as proper relation algebras where a proper relation algebra has binary relations as elements and the algebra is singly-typed. Here, the intensional conjunction, which was to represent relational composition in Chin and Tarski, spans three different local algebras, thus the term distributed in the title. Since we do not rely on proper relation algebras, we are free to re-express the algebras as typed. In doing so, we allow many different intensional conjunction operators. We construct a typed logic over these algebras, also known as heterogeneous algebras of Birkhoff and Lipson. The logic can be seen as a form of relevance logic with a classical negation connective where the Routley-Meyer star operator is reified as a converse connective in the logic. Relevance logic itself is not typed but our work shows how it can be made so. Some of the properties of classical relevance logic are weakened from Routley-Meyer’s version which is too strong for a logic over relation algebras.

We present several new concepts and results on conditional term rewriting within the general framework of order-sorted rewrite theories (OSRTs), which support types, subtypes and rewriting modulo axioms, and contains the more restricted framework of conditional term rewriting systems (CTRSs) as a special case. The concepts shed light on several subtle issues about conditional rewriting and conditional termination. We point out that the notions of irreducible term and of normal form, which coincide for unconditional rewriting, have been conflated for conditional rewriting but are in fact totally different notions. Normal form is a stronger concept. We call any rewrite theory where all irreducible terms are normal forms a normal theory. We argue that normality is essential to have good executability and computability properties. Therefore we call all other theories abnormal, freaks of nature to be avoided. The distinction between irreducible terms and normal forms helps in clarifying various notions of strong and weak termination. We show that abnormal theories can be terminating in various, equally abnormal ways; and argue that any computationally meaningful notion of strong or weak conditional termination should be a property of normal theories. In particular we define the notion of a weakly operationally terminating (or weakly normalizing) OSRT, discuss several evaluation mechanisms to compute normal forms in such theories, and investigate general conditions under which the rewriting-based operational semantics and the initial algebra semantics of a confluent, weakly normalizing OSRT coincide thanks to a notion of canonical term algebra. Finally, we investigate appropriate conditions and proof methods to ensure that a rewrite theory is normal; and characterize the stronger property of a rewrite theory being operationally terminating in terms of a natural generalization of the notion of quasidecreasing order. (C) 2015 Elsevier Inc. All rights reserved., We thank the anonymous referees for their constructive criticism and helpful comments. This work has been partially supported by NSF grant CNS 13-19109. Salvador Lucas' research was developed during a sabbatical year at UIUC and was also supported by the EU (FEDER), Spanish MINECO projects TIN2010-21062-C02-02 and TIN 2013-45732-C4-1-P, and GV grant BEST/2014/026 and project PROMETEO/2011/052.

From a general algebraic point of view, this paper aims at providing an algebraic analysis for binary lattice-valued relations based on lattice implication algebras--a kind of lattice-valued propositional logical algebra. By abstracting away from the concrete lattice-valued relations and the operations on them, such as composition and converse, the notion of lattice-valued relation algebra is introduced, LRA for short. The reduct of an LRA is a lattice implication algebra. Such an algebra generalizes Boolean relation algebras by general distributive lattices and can provide a fundamental algebraic theory for establishing lattice-valued first-order logic. Some important results are generalized from the classical case. The notion of cylindric filter is introduced and the generated cylindric filters are characterized.

This paper presents an algebraic language for fundamental elements of quantum information theory (the density operators), based in the properties of a Clifford algebra of signature (n,3n). We prove that the new description of these elements preserves the same mathematical properties obtained with the classical description. We also extend some results presented in the literature that relate Clifford algebra and quantum information.