Forkable regular expressions

DOI10.1007/978-3-319-30000-9_15MaRDI QIDQ2798720zbMATH OpenOpenAlexFDO

Authors Martin Sulzmann, Peter J. Thiemann

Publication date 13 April 2016

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

automataderivativesforkable expressions

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 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.

Recommendations

• Pattern expressions and pattern automata
• Regular-expression derivatives re-examined
• scientific article; zbMATH DE number 751137
• Constrained expressions and their derivatives
• The fork calculus

Cited in

(2)

• Derivatives for Enhanced Regular Expressions
• Static trace-based deadlock analysis for synchronous Mini-Go

This page was built for publication: Forkable regular expressions

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