Relevant bibliographies by topics / Equational axiomatisation

Academic literature on the topic '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:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources 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.

Journal articles on the topic "Equational axiomatisation"

1

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
2

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
3

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
4

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
5

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
6

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
7

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
8

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
9

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
10

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
More sources

Dissertations / Theses on the topic "Equational axiomatisation"

1

ABBADINI, MARCO. "ON THE AXIOMATISABILITY OF THE DUAL OF COMPACT ORDERED SPACES." Doctoral thesis, Università degli Studi di Milano, 2021. http://hdl.handle.net/2434/812809.

Full text
Abstract:
We 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 show 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, (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 D. Mundici: our result asserts that the category of unital commutative distributive lattice-ordered monoids is equivalent to the category of what we call MV-monoidal algebras. Our proof is independent of Mundici's theorem.
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Equational axiomatisation"

1

Piedeleu, Robin, and Fabio Zanasi. "A String Diagrammatic Axiomatisation of Finite-State Automata." In Lecture Notes in Computer Science, 469–89. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-71995-1_24.

Full text
Abstract:
AbstractWe 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— a result which is provably impossible for the one-dimensional syntax of regular expressions. 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
2

Caltais, Georgiana, Hossein Hojjat, Mohammad Reza Mousavi, and Hünkar Can Tunç. "DyNetKAT: An Algebra of Dynamic Networks." In Lecture Notes in Computer Science, 184–204. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-030-99253-8_10.

Full text
Abstract:
AbstractWe introduce a formal language for specifying dynamic updates for Software Defined Networks. Our language builds upon Network Kleene Algebra with Tests (NetKAT) and adds constructs for synchronisations and multi-packet behaviour to capture the interaction between the control- and data-plane in dynamic updates. We provide a sound and ground-complete axiomatisation of our language. We exploit the equational theory and provide an efficient method for reasoning about safety properties. We implement our equational theory in DyNetiKAT – a tool prototype, based on the Maude Rewriting Logic and the NetKAT tool, and apply it to a case study. We show that we can analyse the case study for networks with hundreds of switches using our tool prototype.
APA, Harvard, Vancouver, ISO, and other styles
3

Wilson, Paul, and Fabio Zanasi. "Categories of Differentiable Polynomial Circuits for Machine Learning." In Graph Transformation, 77–93. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-09843-7_5.

Full text
Abstract:
AbstractReverse derivative categories (RDCs) have recently been shown to be a suitable semantic framework for studying machine learning algorithms. Whereas emphasis has been put on training methodologies, less attention has been devoted to particular model classes: the concrete categories whose morphisms represent machine learning models. In this paper we study presentations by generators and equations of classes of RDCs. In particular, we propose polynomial circuits as a suitable machine learning model. We give an axiomatisation for these circuits and prove a functional completeness result. Finally, we discuss the use of polynomial circuits over specific semirings to perform machine learning with discrete values.
APA, Harvard, Vancouver, ISO, and other styles
4

Boisseau, Guillaume, and Robin Piedeleu. "Graphical Piecewise-Linear Algebra." In Lecture Notes in Computer Science, 101–19. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-030-99253-8_6.

Full text
Abstract:
AbstractGraphical (Linear) Algebra is a family of diagrammatic languages allowing to reason about different kinds of subsets of vector spaces compositionally. It has been used to model various application domains, from signal-flow graphs to Petri nets and electrical circuits. In this paper, we introduce to the family its most expressive member to date: Graphical Piecewise-Linear Algebra, a new language to specify piecewise-linear subsets of vector spaces.Like the previous members of the family, it comes with a complete axiomatisation, which means it can be used to reason about the corresponding semantic domain purely equationally, forgetting the set-theoretic interpretation. We show completeness using a single axiom on top of Graphical Polyhedral Algebra, and show that this extension is the smallest that can capture a variety of relevant constructs.Finally, we showcase its use by modelling the behaviour of stateless electronic circuits of ideal elements, a domain that had remained outside the remit of previous diagrammatic languages.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Equational axiomatisation' for particular source types:
Journal articles
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!

To the bibliography