Relevant bibliographies by topics / Equational axiomatisation / Journal articles

Journal articles on the topic 'Equational axiomatisation'

To see the other types of publications on this topic, follow the link: Equational axiomatisation.

Author: Grafiati

Published: 9 March 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 15 journal articles for your research on the topic 'Equational axiomatisation.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

ACETO, LUCA, TAOLUE CHEN, WAN FOKKINK, and ANNA INGOLFSDOTTIR. "On the axiomatisability of priority." Mathematical Structures in Computer Science 18, no. 1 (February 2008): 5–28. http://dx.doi.org/10.1017/s0960129507006524.

Full text

Abstract:

This paper studies the equational theory of bisimulation equivalence over the process algebra BCCSP extended with the priority operator of Baeten, Bergstra and Klop. We prove that, in the presence of an infinite set of actions, bisimulation equivalence has no finite, sound, ground-complete equational axiomatisation over that language. This negative result applies even if the syntax is extended with an arbitrary collection of auxiliary operators, and motivates the study of axiomatisations using equations with action predicates as conditions. In the presence of an infinite set of actions, it is shown that, in general, bisimulation equivalence has no finite, sound, ground-complete axiomatisation consisting of equations with action predicates as conditions over the language studied in this paper. Finally, sufficient conditions on the priority structure over actions are identified that lead to a finite, ground-complete axiomatisation of bisimulation equivalence using equations with action predicates as conditions.

APA, Harvard, Vancouver, ISO, and other styles

Plotkin, Gordon D. "A Complete Equational Axiomatisation of Partial Differentiation." Electronic Notes in Theoretical Computer Science 352 (October 2020): 211–32. http://dx.doi.org/10.1016/j.entcs.2020.09.011.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Barbosa, Luís S., Manuel A. Martins, and Marta Carreteiro. "A Hilbert-Style Axiomatisation for Equational Hybrid Logic." Journal of Logic, Language and Information 23, no. 1 (January 12, 2014): 31–52. http://dx.doi.org/10.1007/s10849-013-9184-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

GRABMAYER, CLEMENS. "A duality between proof systems for cyclic term graphs." Mathematical Structures in Computer Science 17, no. 3 (June 2007): 439–84. http://dx.doi.org/10.1017/s0960129507006111.

Full text

Abstract:

This paper presents a proof-theoretic observation about two kinds of proof systems for bisimilarity between cyclic term graphs.First we consider proof systems for demonstrating that μ term specifications of cyclic term graphs have the same tree unwinding. We establish a close connection between adaptations for μ terms over a general first-order signature of the coinductive axiomatisation of recursive type equivalence by Brandt and Henglein (Brandt and Henglein 1998) and of a proof system by Ariola and Klop (Ariola and Klop 1995) for consistency checking. We show that there exists a simple duality by mirroring between derivations in the former system and formalised consistency checks, which are called ‘consistency unfoldings', in the latter. This result sheds additional light on the axiomatisation of Brandt and Henglein: it provides an alternative soundness proof for the adaptation considered here.We then outline an analogous duality result that holds for a pair of similar proof systems for proving that equational specifications of cyclic term graphs are bisimilar.

APA, Harvard, Vancouver, ISO, and other styles

ADÁMEK, JIŘÍ, STEFAN MILIUS, and JIŘÍ VELEBIL. "Elgot theories: a new perspective on the equational properties of iteration." Mathematical Structures in Computer Science 21, no. 2 (March 25, 2011): 417–80. http://dx.doi.org/10.1017/s0960129510000496.

Full text

Abstract:

Bloom and Ésik's concept of iteration theory summarises all equational properties that iteration has in common applications, for example, in domain theory, where to every system of recursive equations, the least solution is assigned. This paper shows that in the coalgebraic approach to iteration, the more appropriate concept is that of a functorial iteration theory (called Elgot theory). These theories have a particularly simple axiomatisation, and all well-known examples of iteration theories are functorial. Elgot theories are proved to be monadic over the category of sets in context (or, more generally, the category of finitary endofunctors of a locally finitely presentable category). This demonstrates that functoriality is an equational property from the perspective of sets in context. In contrast, Bloom and Ésik worked in the base category of signatures rather than sets in context, and there iteration theories are monadic but Elgot theories are not. This explains why functoriality was not included in the definition of iteration theories.

APA, Harvard, Vancouver, ISO, and other styles

HAMANA, MAKOTO, KAZUTAKA MATSUDA, and KAZUYUKI ASADA. "The algebra of recursive graph transformation language UnCAL: complete axiomatisation and iteration categorical semantics." Mathematical Structures in Computer Science 28, no. 2 (October 24, 2016): 287–337. http://dx.doi.org/10.1017/s096012951600027x.

Full text

Abstract:

The aim of this paper is to provide mathematical foundations of a graph transformation language, called UnCAL, using categorical semantics of type theory and fixed points. About 20 years ago, Bunemanet al. developed a graph database query language UnQL on the top of a functional meta-language UnCAL for describing and manipulating graphs. Recently, the functional programming community has shown renewed interest in UnCAL, because it provides an efficient graph transformation language which is useful for various applications, such as bidirectional computation.In order to make UnCAL more flexible and fruitful for further extensions and applications, in this paper, we give a more conceptual understanding of UnCAL using categorical semantics. Our general interest of this paper is to clarify what is the algebra of UnCAL. Thus, we give an equational axiomatisation and categorical semantics of UnCAL, both of which are new. We show that the axiomatisation is complete for the original bisimulation semantics of UnCAL. Moreover, we provide a clean characterisation of the computation mechanism of UnCAL called ‘structural recursion on graphs’ using our categorical semantics. We show a concrete model of UnCAL given by the λG-calculus, which shows an interesting connection to lazy functional programming.

APA, Harvard, Vancouver, ISO, and other styles

Abbadini, Marco. "On the Axiomatisability of the Dual of Compact Ordered Spaces." Bulletin of Symbolic Logic 27, no. 4 (December 2021): 526. http://dx.doi.org/10.1017/bsl.2021.54.

Full text

Abstract:

AbstractWe prove that the category of Nachbin’s compact ordered spaces and order-preserving continuous maps between them is dually equivalent to a variety of algebras, with operations of at most countable arity. Furthermore, we observe that the countable bound on the arity is the best possible: the category of compact ordered spaces is not dually equivalent to any variety of finitary algebras. Indeed, the following stronger results hold: the category of compact ordered spaces is not dually equivalent to (i) any finitely accessible category, (ii) any first-order definable class of structures, and (iii) any class of finitary algebras closed under products and subalgebras. An explicit equational axiomatisation of the dual of the category of compact ordered spaces is obtained; in fact, we provide a finite one, meaning that our description uses only finitely many function symbols and finitely many equational axioms. In preparation for the latter result, we establish a generalisation of a celebrated theorem by Mundici: our result—whose proof is independent of Mundici’s theorem—asserts that the category of unital commutative distributive lattice-ordered monoids is equivalent to the category of what we call MV-monoidal algebras.Abstract taken directly from the thesis.E-mail: marco.abbadini.uni@gmail.comURL: https://air.unimi.it/retrieve/handle/2434/812809/1698986/phd_unimi_R11882.pdf

APA, Harvard, Vancouver, ISO, and other styles

MIMRAM, SAMUEL. "The structure of first-order causality." Mathematical Structures in Computer Science 21, no. 1 (January 24, 2011): 65–110. http://dx.doi.org/10.1017/s0960129510000459.

Full text

Abstract:

Game semantics describe the interactive behaviour of proofs by interpreting formulas as games on which proofs induce strategies. Such a semantics is introduced here for capturing dependencies induced by quantifications in first-order propositional logic. One of the main difficulties that has to be faced during the elaboration of this kind of semantics is to characterise definable strategies, that is, strategies that actually behave like a proof. This is usually done by restricting the model to strategies satisfying subtle combinatorial conditions, whose preservation under composition is often difficult to show. In this paper we present an original methodology to achieve this task, which requires a combination of advanced tools from game semantics, rewriting theory and categorical algebra. We introduce a diagrammatic presentation of the monoidal category of definable strategies of our model using generators and relations: these strategies can be generated from a finite set of atomic strategies, and the equality between strategies admits a finite axiomatisation, and this equational structure corresponds to a polarised variation of the bialgebra notion. The work described in this paper thus forms a bridge between algebra and denotational semantics in order to reveal the structure of dependencies induced by first-order quantifiers, and lays the foundations for a mechanised analysis of causality in programming languages.

APA, Harvard, Vancouver, ISO, and other styles

Carette, Titouan, Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. "Completeness of Graphical Languages for Mixed State Quantum Mechanics." ACM Transactions on Quantum Computing 2, no. 4 (December 31, 2021): 1–28. http://dx.doi.org/10.1145/3464693.

Full text

Abstract:

There exist several graphical languages for quantum information processing, like quantum circuits, ZX-calculus, ZW-calculus, and so on. Each of these languages forms a †-symmetric monoidal category (†-SMC) and comes with an interpretation functor to the †-SMC of finite-dimensional Hilbert spaces. In recent years, one of the main achievements of the categorical approach to quantum mechanics has been to provide several equational theories for most of these graphical languages, making them complete for various fragments of pure quantum mechanics. We address the question of how to extend these languages beyond pure quantum mechanics to reason about mixed states and general quantum operations, i.e., completely positive maps. Intuitively, such an extension relies on the axiomatisation of a discard map that allows one to get rid of a quantum system, an operation that is not allowed in pure quantum mechanics. We introduce a new construction, the discard construction , which transforms any †-symmetric monoidal category into a symmetric monoidal category equipped with a discard map. Roughly speaking this construction consists in making any isometry causal. Using this construction, we provide an extension for several graphical languages that we prove to be complete for general quantum operations. However, this construction fails for some fringe cases like Clifford+T quantum mechanics, as the category does not have enough isometries.

APA, Harvard, Vancouver, ISO, and other styles

Hofmann, Martin. "Sound and complete axiomatisations of call-by-value control operators." Mathematical Structures in Computer Science 5, no. 4 (December 1995): 461–82. http://dx.doi.org/10.1017/s0960129500001195.

Full text

Abstract:

We formulate a typed version of call-by-value λ-calculus containing variants of Felleisen's control operators A and C that provide explicit access to continuations and logically extend the propositions-as-types correspondence to classical propositional logic. We give an equational theory for this calculus, which is shown to be sound and complete with respect to a class of categorical models based on continuation-passing-style semantics.

APA, Harvard, Vancouver, ISO, and other styles

Hirsch, Robin, and Ian Hodkinson. "Step by step – Building representations in algebraic logic." Journal of Symbolic Logic 62, no. 1 (March 1997): 225–79. http://dx.doi.org/10.2307/2275740.

Full text

Abstract:

AbstractWe consider the problem of finding and classifying representations in algebraic logic. This is approached by letting two players build a representation using a game. Homogeneous and universal representations are characterized according to the outcome of certain games. The Lyndon conditions defining representable relation algebras (for the finite case) and a similar schema for cylindric algebras are derived. Finte relation algebras with homogeneous representations are characterized by first order formulas. Equivalence games are defined, and are used to establish whether an algebra is ω-categorical. We have a simple proof that the perfect extension of a representable relation algebra is completely representable.An important open problem from algebraic logic is addressed by devising another two-player game, and using it to derive equational axiomatisations for the classes of all representable relation algebras and representable cylindric algebras.Other instances of this approach are looked at, and include the step by step method.

APA, Harvard, Vancouver, ISO, and other styles

Aceto, Luca, Valentina Castiglioni, Anna Ingolfsdottir, Bas Luttik, and Mathias R. Pedersen. "On the Axiomatisability of Parallel Composition." Logical Methods in Computer Science Volume 18, Issue 1 (January 19, 2022). http://dx.doi.org/10.46298/lmcs-18(1:15)2022.

Full text

Abstract:

This paper studies the existence of finite equational axiomatisations of the interleaving parallel composition operator modulo the behavioural equivalences in van Glabbeek's linear time-branching time spectrum. In the setting of the process algebra BCCSP over a finite set of actions, we provide finite, ground-complete axiomatisations for various simulation and (decorated) trace semantics. We also show that no congruence over BCCSP that includes bisimilarity and is included in possible futures equivalence has a finite, ground-complete axiomatisation; this negative result applies to all the nested trace and nested simulation semantics.

APA, Harvard, Vancouver, ISO, and other styles

Aceto, Luca, Valentina Castiglioni, Wan Fokkink, Anna Ingólfsdóttir, and Bas Luttik. "Are Two Binary Operators Necessary to Obtain a Finite Axiomatisation of Parallel Composition?" ACM Transactions on Computational Logic, April 20, 2022. http://dx.doi.org/10.1145/3529535.

Full text

Abstract:

Bergstra and Klop have shown that bisimilarity has a finite equational axiomatisation over ACP/CCS extended with the binary left and communication merge operators. Moller proved that auxiliary operators are necessary to obtain a finite axiomatisation of bisimilarity over CCS, and Aceto et al. showed that this remains true when Hennessy’s merge is added to that language. These results raise the question of whether there is one auxiliary binary operator whose addition to CCS leads to a finite axiomatisation of bisimilarity. We contribute to answering this question in the simplified setting of the recursion-, relabelling-, and restriction-free fragment of CCS. We formulate three natural assumptions pertaining to the operational semantics of auxiliary operators and their relationship to parallel composition, and prove that an auxiliary binary operator facilitating a finite axiomatisation of bisimilarity in the simplified setting cannot satisfy all three assumptions.

APA, Harvard, Vancouver, ISO, and other styles

Piedeleu, Robin, and Fabio Zanasi. "A Finite Axiomatisation of Finite-State Automata Using String Diagrams." Logical Methods in Computer Science Volume 19, Issue 1 (February 15, 2023). http://dx.doi.org/10.46298/lmcs-19(1:13)2023.

Full text

Abstract:

We develop a fully diagrammatic approach to finite-state automata, based on reinterpreting their usual state-transition graphical representation as a two-dimensional syntax of string diagrams. In this setting, we are able to provide a complete equational theory for language equivalence, with two notable features. First, the proposed axiomatisation is finite. Second, the Kleene star is a derived concept, as it can be decomposed into more primitive algebraic blocks.

APA, Harvard, Vancouver, ISO, and other styles

Bergstra, Jan A., and John V. Tucker. "Eager Equality for Rational Number Arithmetic." ACM Transactions on Computational Logic, January 17, 2023. http://dx.doi.org/10.1145/3580365.

Full text

Abstract:

Eager equality for algebraic expressions over partial algebras distinguishes or separates terms only if both have defined values and they are different. We consider arithmetical algebras with division as a partial operator, called meadows, and focus on algebras of rational numbers. To study eager equality we use common meadows, which are totalisations of partial meadows by means of absorbtive elements. An axiomatisation of common meadows is the basis of an axiomatisation of eager equality as a predicate on a common meadow. Applied to the rational numbers, we prove completeness and decidability of the equational theory of eager equality. To situate eager equality theoretically, we consider two other partial equalities of increasing strictness: Kleene equality, which is equivalent to the native equality of common meadows, and one we call cautious equality. Our methods of analysis for eager equality are quite general and so we apply them to these two other partial equalities; and, in addition to common meadows, we use three other kinds of algebra designed to totalise division. In summary, we are able to compare 13 forms of equality for the partial meadow of rational numbers. We focus on the decidability of the equational theories of these equalities. We show that for the four total algebras, eager and cautious equality are decidable. We also show that for others the Diophantine Problem over the rationals is one-one computably reducible to their equational theories. The Diophantine Problem for rationals is a longstanding open problem. Thus, eager equality has substantially less complex semantics.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!