A connection between concurrency and language theory

DOI10.1016/J.ENTCS.2013.09.011MaRDI QIDQ265802zbMATH OpenOpenAlexWikidataFDO

Authors Zoltán Ésik

Publication date 12 April 2016

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

context-free languagesfixed-point operationsiteration theoriesregular tree languagessimulation equivalencesynchronization trees

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: We show that three fixed point structures equipped with (sequential) composition, a sum operation, and a fixed point operation share the same valid equations. These are the theories of (context-free) languages, (regular) tree languages, and simulation equivalence classes of (regular) synchronization trees (or processes). The results reveal a close relationship between classical language theory and process algebra.

Recommendations

• scientific article; zbMATH DE number 2087210
• Connections between two theories of concurrency: Metric spaces and synchronization trees
• Process languages and nets
• Iteration theories of synchronization trees
• scientific article; zbMATH DE number 3905854

Cites work

• scientific article; zbMATH DE number 1670485 (Why is no real title available?)
• scientific article; zbMATH DE number 3716792 (Why is no real title available?)
• scientific article; zbMATH DE number 3731311 (Why is no real title available?)
• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 46995 (Why is no real title available?)
• scientific article; zbMATH DE number 3512082 (Why is no real title available?)
• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 1231455 (Why is no real title available?)
• scientific article; zbMATH DE number 1136085 (Why is no real title available?)
• scientific article; zbMATH DE number 2040320 (Why is no real title available?)
• scientific article; zbMATH DE number 2080931 (Why is no real title available?)
• Axiomatizing rational power series over natural numbers
• Axiomatizing the equational theory of regular tree languages
• Axiomatizing weighted synchronization trees and weighted bisimilarity
• Completeness of Park induction
• Continuous Additive Algebras and Injective Simulations of Synchronization Trees
• Deciding bisimilarity is P-complete
• Equational axioms for probabilistic bisimilarity
• Equational axioms for regular sets
• Equational logic of circular data type specification
• Equational properties of iteration in algebraically complete categories
• FUNCTORIAL SEMANTICS OF ALGEBRAIC THEORIES
• Free inductive \(K\)-semialgebras
• Free iterative and iteration \(K\)-semialgebras
• Group axioms for iteration
• Handbook of weighted automata
• IO and OI. II
• Initial Algebra Semantics and Continuous Algebras
• Iteration Grove Theories with Applications
• Iteration theories of synchronization trees
• Matrix and matricial iteration theories. I
• Residuated Park theories
• Solutions of the Iteration Equation and Extensions of the Scalar Iteration Operation
• Synchronization trees
• The equational logic of fixed points
• Varieties of ordered algebras

Cited in

(5)

• Equational properties of fixed-point operations in Cartesian categories: an overview
• Connections between two theories of concurrency: Metric spaces and synchronization trees
• Equational properties of fixed point operations in Cartesian categories: an overview
• Aperiodic languages in concurrency monoids
• Algebraic Methodology and Software Technology

This page was built for publication: A connection between concurrency and language theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q265802)