A connection between concurrency and language theory

2013/02/28 by Zoltán Ésik, Esik, Zoltan
Computer Science · #06F99 #08A70 #68Q70 #F.4 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems

paper · pdf · doi:10.48550/arxiv.1303.0044

openalex publication_date 2013/02/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• Computation and Concurrency
• The Nature of Concurrency
• Algebraic laws for nondeterminism and concurrency
• Minimal Translations from Synchronous Communication to Synchronizing Locks (Extended Version)
• A synchronous program algebra: a basis for reasoning about shared-memory\n and event-based concurrency