On series-parallel pomset languages: rationality, context-freeness and automata

DOI10.1016/J.JLAMP.2018.12.001zbMath1417.68134arXiv1812.03058OpenAlexW3098007364MaRDI QIDQ1734519

Alexandra Silva, Tobias Kappé, Paul Brunet, Fabio Zanasi, Bas Luttik

Publication date: 27 March 2019

Published in: Journal of Logical and Algebraic Methods in Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1812.03058

zbMATH Keywords

concurrencyKleene algebraKleene theoremBrzozowski derivativespomset automataseries-rational expressions

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Grammars and rewriting systems (68Q42) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Related Items (3)

Branching pomsets: design, expressiveness and applications to choreographies ⋮ Learning pomset automata ⋮ Preface to the special issue on open problems in concurrency theory

Uses Software

• NetKAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Concurrent Kleene algebra with tests and branching automata
• Synchronous Kleene algebra
• The equational theory of pomsets
• A completeness theorem for Kleene algebras and the algebra of regular events
• Series-parallel languages and the bounded-width property
• Concurrent Kleene algebra: free model and completeness
• Coalgebraic Bisimulation-Up-To
• Deciding Synchronous Kleene Algebra with Derivatives
• Concurrent Kleene Algebra
• Petri Automata for Kleene Allegories
• NetKAT
• Concurrent Kleene Algebra with Tests
• Completeness Theorems for Bi-Kleene Algebras and Series-Parallel Rational Pomset Languages
• Three models for the description of language
• A note on undecidable properties of formal languages
• Programming Techniques: Regular expression search algorithm
• Derivatives of Regular Expressions

This page was built for publication: On series-parallel pomset languages: rationality, context-freeness and automata