A connection between concurrency and language theory

DOI10.1016/J.ENTCS.2013.09.011zbMATH Open1334.68116arXiv1303.0044OpenAlexW2161360624WikidataQ113317964 ScholiaQ113317964MaRDI QIDQ265802FDOQ265802

Zoltán Ésik

Publication date: 12 April 2016

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Equational properties of iteration in algebraically complete categories
• Deciding bisimilarity is P-complete
• Iteration theories of synchronization trees
• Varieties of ordered algebras
• IO and OI. II
• Group axioms for iteration
• Synchronization trees
• The equational logic of fixed points
• Completeness of Park induction
• Equational logic of circular data type specification
• Matrix and matricial iteration theories. I
• Axiomatizing rational power series over natural numbers
• Axiomatizing weighted synchronization trees and weighted bisimilarity
• Equational Axioms for Probabilistic Bisimilarity
• Residuated Park theories
• Iteration Grove Theories with Applications
• Free inductive \(K\)-semialgebras
• Solutions of the Iteration Equation and Extensions of the Scalar Iteration Operation
• Free iterative and iteration \(K\)-semialgebras
• Initial Algebra Semantics and Continuous Algebras
• Equational axioms for regular sets
• Continuous Additive Algebras and Injective Simulations of Synchronization Trees
• FUNCTORIAL SEMANTICS OF ALGEBRAIC THEORIES
• Handbook of weighted automata
• Axiomatizing the equational theory of regular tree languages

Cited In (3)

• Equational properties of fixed-point operations in cartesian categories: An overview
• Aperiodic languages in concurrency monoids
• Equational Properties of Fixed Point Operations in Cartesian Categories: An Overview

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)