2015/10/25 by Martin Sulzmann, Sulzmann, Martin, Peter Thiemann +1
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #Programming Languages (cs.PL) #cs.FL #cs.LO #cs.PL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1510.07293
12 pages plus technical appendix, to appear in LATA 2016
openalex publication_date 2015/10/25 · arxiv created 2015/12/08 · arxiv updated 2015/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider forkable regular expressions, which enrich regular expressions with a fork operator, to establish a formal basis for static and dynamic analysis of the communication behavior of concurrent programs. We define a novel compositional semantics for forkable expressions, establish their fundamental properties, and define derivatives for them as a basis for the generation of automata, for matching, and for language containment tests. Forkable expressions may give rise to non-regular languages, in general, but we identify sufficient conditions on expressions that guarantee finiteness of the automata construction via derivatives.