Better automata through process algebra

DOI10.1007/978-3-031-15629-8_7MaRDI QIDQ6163884zbMATH OpenOpenAlexFDO

Authors Rance Cleaveland

Publication date 26 July 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

finite automataoperational semanticsprocess algebraregular expressions

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semantics in the theory of computing (68Q55) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: This paper shows how the use of Structural Operational Semantics (SOS) in the style popularized by the process-algebra community can lead to a more succinct and useful construction for building finite automata from regular expressions. Such constructions have been known for decades, and form the basis for the proofs of one direction of Kleene's Theorem. The purpose of the new construction is, on the one hand, to show students how small automata can be constructed, without the need for empty transitions, and on the other hand to show how the construction method admits closure proofs of regular languages with respect to other operators as well. These results, while not theoretically surprising, point to an additional influence of process-algebraic research: in addition to providing fundamental insights into the nature of concurrent computation, it also sheds new light on old, well-known constructions in automata theory.

Recommendations

• Structural operational semantics.
• A regular viewpoint on processes and algebra
• scientific article; zbMATH DE number 177531
• CSP for parallelising Brzozowski's DFA construction algorithm
• scientific article; zbMATH DE number 177252

Cites work

• A calculus of communicating systems
• A characterization of regular expressions under bisimulation
• A Coinductive Reformulation of Milner's Proof System for Regular Expressions Modulo Bisimilarity
• A complete inference system for a class of regular behaviours
• An overview of the mCRL2 toolset and its recent advances
• CCS expressions, finite state processes, and three problems of equivalence
• Derivatives of Regular Expressions
• From regular expressions to deterministic automata
• Generic tools for verifying concurrent systems
• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• scientific article; zbMATH DE number 4030999 (Why is no real title available?)
• scientific article; zbMATH DE number 1306878 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• Programming Techniques: Regular expression search algorithm
• The origins of structural operational semantics

Cited in

(1)

• Integrated Formal Methods

This page was built for publication: Better automata through process algebra

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