A completeness theorem for Kleene algebras and the algebra of regular events
From MaRDI portal
Publication:1327385
DOI10.1006/inco.1994.1037zbMath0806.68082OpenAlexW2163152086WikidataQ56140181 ScholiaQ56140181MaRDI QIDQ1327385
Publication date: 19 June 1994
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.1994.1037
Applications of universal algebra in computer science (08A70) Algebraic theory of languages and automata (68Q70)
Related Items (only showing first 100 items - show all)
Algebras of modal operators and partial correctness ⋮ An algebraic approach to computations with progress ⋮ Canonical finite models of Kleene algebra with tests ⋮ Developments in concurrent Kleene algebra ⋮ Concurrent Kleene algebra with tests and branching automata ⋮ Factor theory and the unity of opposites ⋮ An exercise on the generation of many-valued dynamic logics ⋮ Axiomatizing recursion-free, regular monitors ⋮ Normal design algebra ⋮ Axiomatizing the equational theory of regular tree languages ⋮ Optimistic synchronization-based state-space reduction ⋮ Axiomatizing rational power series over natural numbers ⋮ Inductive semimodules and the vector modules over them. ⋮ A congruence on the semiring of normal tropical matrices ⋮ Proof Pearl: regular expression equivalence and relation algebra ⋮ An equational axiomatization for multi-exit iteration ⋮ Axiomatizing the identities of binoid languages ⋮ Nonaxiomatisability of equivalences over finite state processes ⋮ Abstract representation theorems for demonic refinement algebras ⋮ Algebraic notions of nontermination: Omega and divergence in idempotent semirings ⋮ Equational properties of iteration in algebraically complete categories ⋮ Free inductive \(K\)-semialgebras ⋮ Graded epistemic logic with public announcement ⋮ The equational logic of fixed points ⋮ Completeness of Park induction ⋮ Typing theorems of omega algebra ⋮ Left omega algebras and regular equations ⋮ Programming and automating mathematics in the Tarski-Kleene hierarchy ⋮ Hopscotch -- reaching the target hop by hop ⋮ Relations into algebras of probabilistic distributions ⋮ A bialgebraic approach to automata and formal language theory ⋮ The multiplicative fragment of the Yanov equational theory ⋮ Free iterative and iteration \(K\)-semialgebras ⋮ On the equational definition of the least prefixed point. ⋮ Internal axioms for domain semirings ⋮ In praise of algebra ⋮ Dijkstra, Floyd and Warshall meet Kleene ⋮ On algebra of languages representable by vertex-labeled graphs ⋮ Override and update ⋮ Second-order properties of undirected graphs ⋮ Relation-algebraic verification of Borůvka's minimum spanning tree algorithm ⋮ Completeness for flat modal fixpoint logics ⋮ Relational characterisations of paths ⋮ Free Kleene algebras with domain ⋮ Axiomatizability of positive algebras of binary relations ⋮ Enabledness and termination in refinement algebra ⋮ Axiomatizing weighted synchronization trees and weighted bisimilarity ⋮ Completions of \(\mu \)-algebras ⋮ The equational theory of Kleene lattices ⋮ Local variable scoping and Kleene algebra with tests ⋮ Relational semigroupoids: abstract relation-algebraic interfaces for finite relations between infinite types ⋮ Models of nondeterministic regular expressions ⋮ Infinitary action logic: complexity, models and grammars ⋮ Domain and range for angelic and demonic compositions ⋮ On series-parallel pomset languages: rationality, context-freeness and automata ⋮ A string diagrammatic axiomatisation of finite-state automata ⋮ Kleene star, subexponentials without contraction, and infinite computations ⋮ Dynamic algebras: Examples, constructions, applications ⋮ Verifying minimum spanning tree algorithms with Stone relation algebras ⋮ On the expressiveness of single-pass instruction sequences ⋮ A sketch of a dynamic epistemic semiring ⋮ Dual choice and iteration in an abstract algebra of action ⋮ Fixing Zeno gaps ⋮ A coalgebraic approach to Kleene algebra with tests ⋮ Fixpoints for general correctness ⋮ Concurrent Kleene algebra and its foundations ⋮ Collagories: relation-algebraic reasoning for gluing constructions ⋮ Normal forms in total correctness for while programs and action systems ⋮ Complete axiomatizations for XPath fragments ⋮ Refinement algebra for probabilistic programs ⋮ Is observational congruence on \(\mu \)-expressions axiomatisable in equational Horn logic? ⋮ Synchronous Kleene algebra ⋮ Algebras for iteration and infinite computations ⋮ An algebraic framework for minimum spanning tree problems ⋮ On the complexity of reasoning in Kleene algebra ⋮ Left-handed completeness ⋮ Explaining safety failures in NetKAT ⋮ A note on an expressiveness hierarchy for multi-exit iteration ⋮ Invariants and closures in the theory of rewrite systems ⋮ Algebra and theory of order-deterministic pomsets ⋮ On a question of A. Salomaa The equational theory of regular expressions over a singleton alphabet is not finitely based ⋮ Group axioms for iteration ⋮ Equational theories for automata ⋮ Automated verification of refinement laws ⋮ Language preorder as a precongruence ⋮ Automata, Boolean matrices, and ultimate periodicity. ⋮ On equations for union-free regular languages ⋮ Efficient and flexible matching of recursive types ⋮ A semantics and a logic for \textit{Fuzzy Arden Syntax} ⋮ Extended transitive separation logic ⋮ Infinite executions of lazy and strict computations ⋮ Deciding Kleene algebra terms equivalence in Coq ⋮ Completeness results for omega-regular algebras ⋮ Denotational fixed-point semantics for constructive scheduling of synchronous concurrency ⋮ On the fine-structure of regular algebra ⋮ Regular algebra applied to language problems ⋮ Kleene under a modal demonic star ⋮ Kleene modules and linear languages ⋮ Abstract abstract reduction ⋮ Relational semantics for Kleene logic and action logic
This page was built for publication: A completeness theorem for Kleene algebras and the algebra of regular events
