From regular expressions to deterministic automata

DOI10.1016/0304-3975(86)90088-5zbMath0626.68043OpenAlexW2092860912MaRDI QIDQ580983

Ravi Sethi, Gérard Berry

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/inria-00075904/file/RR-0649.pdf

zbMATH Keywords

efficient algorithmalgorithm for constructing a finite automaton from a regular expressionDerivatives of regular expressionsmarked expression

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (65)

FROM C-CONTINUATIONS TO NEW QUADRATIC ALGORITHMS FOR AUTOMATON SYNTHESIS ⋮ Derivatives of Regular Expressions and an Application ⋮ Two Algorithms For Languages Recognized By Graph Algebras ⋮ Glushkov Construction For Series: The Non Commutative Case ⋮ THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS ⋮ Prolog infinite trees and automata ⋮ Minimized Thompson NFA ⋮ Passive testing with asynchronous communications and timestamps ⋮ Manipulation of regular expressions using derivatives: an overview ⋮ The validation of SGML content models ⋮ Equations and regular-like expressions for afa ⋮ Hardware Implementations of Finite Automata and Regular Expressions ⋮ From Ambiguous Regular Expressions to Deterministic Parsing Automata ⋮ Deterministic regular languages ⋮ From regular expressions to DFA's using compressed NFA's ⋮ Better automata through process algebra ⋮ PuRSUE -- from specification of robotic environments to synthesis of controllers ⋮ A Decision Procedure for Regular Membership and Length Constraints over Unbounded Strings ⋮ Automata for regular expressions with shuffle ⋮ Construction of Tree Automata from Regular Expressions ⋮ Unnamed Item ⋮ Follow automata. ⋮ Reducing NFAs by invariant equivalences. ⋮ Adding pebbles to weighted automata: easy specification \& efficient evaluation ⋮ Space-Efficient Representations for Glushkov Automata ⋮ Extended to multi-tilde-bar regular expressions and efficient finite automata constructions ⋮ Clocks in dataflow languages ⋮ Partial derivatives of regular expressions and finite automaton constructions ⋮ Local languages and the Berry-Sethi algorithm ⋮ ON THE AVERAGE SIZE OF GLUSHKOV AND PARTIAL DERIVATIVE AUTOMATA ⋮ Compilation of the ELECTRE reactive language into finite transition systems ⋮ Functional dependencies on extended relations defined by regular languages ⋮ Derivatives and Finite Automata of Expressions in Star Normal Form ⋮ NONDETERMINISTIC BIAUTOMATA AND THEIR DESCRIPTIONAL COMPLEXITY ⋮ One-unambiguous regular languages ⋮ One-unambiguous regular languages ⋮ Vacuity in practice: temporal antecedent failure ⋮ Language operations with regular expressions of polynomial size ⋮ A mesh of automata ⋮ NR‐grep: a fast and flexible pattern‐matching tool ⋮ How expressions can code for automata ⋮ From regular expressions to smaller NFAs ⋮ From regular expressions to finite automata^∗ ⋮ Boolean operations and inclusion test for attribute-element constraints ⋮ Kleene Theorems for Product Systems ⋮ A deterministic parsing algorithm for ambiguous regular expressions ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ Regular-expression derivatives re-examined ⋮ Compact representations of automata for regular expression matching ⋮ Position Automaton Construction for Regular Expressions with Intersection ⋮ Hedge Pattern Partial Derivative ⋮ Clausal Tableaux for Hybrid PDL ⋮ Construction of tree automata from regular expressions ⋮ Derivative-Based Diagnosis of Regular Expression Ambiguity ⋮ Adapting functional programs to higher order logic ⋮ Regular expression searching on compressed text ⋮ Automata and rational expressions ⋮ Descriptional complexity of regular languages ⋮ An efficient null-free procedure for deciding regular language membership ⋮ Characterization of Glushkov automata ⋮ Motif statistics. ⋮ Canonical derivatives, partial derivatives and finite automaton constructions. ⋮ Proof-directed program transformation: A functional account of efficient regular expression matching ⋮ Regular expressions into finite automata ⋮ Computing with relational machines

Uses Software

• Esterel

Cites Work

• A complete inference system for a class of regular behaviours
• Programming Techniques: Regular expression search algorithm
• Derivatives of Regular Expressions
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: From regular expressions to deterministic automata