Free shuffle algebras in language varieties

DOI10.1016/0304-3975(95)00230-8zbMath0874.68171OpenAlexW1978996774MaRDI QIDQ671351

Stephen L. Bloom, Zoltán Ésik

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00230-8

zbMATH Keywords

free algebrasshuffle productfree monoidregular subsetsshuffle semirings of languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Applications of universal algebra in computer science (08A70) Semigroups in automata theory, linguistics, etc. (20M35) Semirings (16Y60) Free algebras (08B20)

Related Items

Taming Multirelations, Equivalence of regular binoid expressions and regular expressions denoting binoid languages over free binoids, Developments in concurrent Kleene algebra, Concurrent Kleene algebra with tests and branching automata, Infinite unfair shuffles and associativity, Axiomatizing shuffle and concatenation in languages, Posets with interfaces as a model for concurrency, Nonfinite axiomatizability of shuffle inequalities, Generating Posets Beyond N, Regular binoid expressions and regular binoid languages., On the homomorphism order of labeled posets, Probabilistic rely-guarantee calculus, Labeled posets are universal, Discovering Block-Structured Process Models from Incomplete Event Logs, CCS with Hennessy's merge has no finite-equational axiomatization, Long words: The theory of concatenation and \(\omega\)-power, Synchronous Kleene algebra, Constructing the Views Framework, On Locality and the Exchange Law for Concurrent Processes, Series-parallel languages and the bounded-width property, Test sets for equality of terms in the additive structure of ordinals augmented with right multiplication by \(\omega\), Synchronized shuffles, Rationality in algebras with a series operation, Decidability of split equivalence, The Quest for Equational Axiomatizations of Parallel Composition: Status and Open Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Modeling concurrency with partial orders
• The equational theory of pomsets
• Nonfinite axiomatizability of the equational theory of shuffle
• Varieties of ordered algebras
• Towards action-refinement in process algebras
• Complexity Results for POMSET Languages
• The Recognition of Series Parallel Digraphs
• Languages under concatenation and shuffling
• Free shuffle algebras in language varieties extended abstract
• Nonfinite axiomatizability of shuffle inequalities