Derivatives for Enhanced Regular Expressions

DOI10.1007/978-3-319-40946-7_24MaRDI QIDQ2830228zbMATH OpenOpenAlexFDO

Authors Peter J. Thiemann

Publication date 9 November 2016

Published in Implementation and Application of Automata (Search for Journal in Brave)

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

zbMATH Keywords

automata and logicderivativesregular languages

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45)

Abstract: Regular languages are closed under a wealth of formal language operators. Incorporating such operators in regular expressions leads to concise language specifications, but the transformation of such enhanced regular expressions to finite automata becomes more involved. We present an approach that enables the direct construction of finite automata from regular expressions enhanced with further operators that preserve regularity. Our construction is based on an extension of the theory of derivatives for regular expressions. To retain the standard results about derivatives, we develop a derivability criterion for the compatibility of the extra operators with derivatives. Some derivable operators do not preserve regularity. Derivatives provide a decision procedure for the word problem of regular expressions enhanced with such operators.

Recommendations

• Regular-expression derivatives re-examined
• Derivatives of regular expressions and an application
• Partial derivatives of an extended regular expression
• Computation of regular expression derivatives
• Derivatives of approximate regular expressions
• Manipulation of regular expressions using derivatives: an overview
• Derivatives of quantitative regular expressions
• Derivatives of regular expressions with cuts
• Approximate regular expressions and their derivatives
• Two-sided derivatives for regular expressions and for hairpin expressions

Cites work

• A general framework for the derivation of regular expressions
• Algebra and Coalgebra in Computer Science
• Approximate regular expressions and their derivatives
• Derivatives for regular shuffle expressions
• Derivatives of Regular Expressions
• Forkable regular expressions
• scientific article; zbMATH DE number 2043550 (Why is no real title available?)
• Multi-Tilde-Bar Derivatives
• Parsing with derivatives
• Partial derivatives of an extended regular expression
• Partial derivatives of regular expressions and finite automaton constructions
• Regular-expression derivatives re-examined
• The Average Transition Complexity of Glushkov and Partial Derivative Automata
• Verified decision procedures for MSO on words based on derivatives of regular expressions

Cited in

(4)

• Two-sided derivatives for regular expressions and for hairpin expressions
• Partial derivatives for context-free languages. From -regular expressions to pushdown automata
• POSIX lexing with derivatives of regular expressions
• Simplified parsing expression derivatives

Describes a project that uses

Uses Software

• MSO_Regex_Equivalence

This page was built for publication: Derivatives for Enhanced Regular Expressions

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