Partial derivatives of regular expressions and finite automaton constructions
From MaRDI portal
Publication:672142
DOI10.1016/0304-3975(95)00182-4zbMath0872.68120OpenAlexW2094985106MaRDI QIDQ672142
Publication date: 27 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(95)00182-4
non-deterministic finite automataalgorithm for turning regular expressions into NFA'sBrzozowski's algorithmpartial derivative of a regular expression
Related Items
Constrained multi-tildes, Average complexity of partial derivatives for synchronised shuffle expressions, Unnamed Item, Simplifying regular expressions further, FROM C-CONTINUATIONS TO NEW QUADRATIC ALGORITHMS FOR AUTOMATON SYNTHESIS, Derivatives of Regular Expressions and an Application, Algorithms for Kleene algebra with converse, Unnamed Item, Derived-Term Automata for Extended Weighted Rational Expressions, THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS, ON THE AVERAGE STATE COMPLEXITY OF PARTIAL DERIVATIVE AUTOMATA: AN ANALYTIC COMBINATORICS APPROACH, Rational and Recognisable Power Series, Prefix and Right-Partial Derivative Automata, On the computation of quotients and factors of regular languages, Manipulation of regular expressions using derivatives: an overview, Tree pattern matching from regular tree expressions, Deciding Synchronous Kleene Algebra with Derivatives, Two-Sided Derivatives for Regular Expressions and for Hairpin Expressions, CLP(H):Constraint logic programming for hedges, Fast matching of regular patterns with synchronizing counting, Left is Better Than Right for Reducing Nondeterminism of NFAs, Derivatives and partial derivatives for regular shuffle expressions, A Coinductive Reformulation of Milner's Proof System for Regular Expressions Modulo Bisimilarity, Unnamed Item, Completeness and the finite model property for Kleene algebra, reconsidered, Location automata for regular expressions with shuffle and intersection, A Decision Procedure for Regular Membership and Length Constraints over Unbounded Strings, Efficient weighted expressions conversion, Location automata for synchronised shuffle expressions, Verified decision procedures for MSO on words based on derivatives of regular expressions, Automata for regular expressions with shuffle, On the average complexity of partial derivative transducers, Unnamed Item, Unnamed Item, Construction of Tree Automata from Regular Expressions, Follow automata., Derivatives of rational expressions and related theorems., Reducing NFAs by invariant equivalences., Equational Theories of Abnormal Termination Based on Kleene Algebra, Partial Derivatives for Context-Free Languages, Space-Efficient Representations for Glushkov Automata, Extension of Brzozowski's derivation calculus of rational expressions to series over the free partially commutative monoids, Postfix automata, On the Average State Complexity of Partial Derivative Transducers, Reordering Derivatives of Trace Closures of Regular Languages., Location based automata for expressions with shuffle, Extended to multi-tilde-bar regular expressions and efficient finite automata constructions, ON THE AVERAGE SIZE OF GLUSHKOV AND PARTIAL DERIVATIVE AUTOMATA, Verification and enforcement of access control policies, Unnamed Item, Construction of fuzzy automata from fuzzy regular expressions, Derivatives and Finite Automata of Expressions in Star Normal Form, Almost event-rate independent monitoring, FROM REGULAR WEIGHTED EXPRESSIONS TO FINITE AUTOMATA, Derivatives of rational expressions with multiplicity, A mesh of automata, Multi-tilde-bar expressions and their automata, How expressions can code for automata, From regular expressions to smaller NFAs, From regular expressions to finite automata∗, Antimirov and Mosses’s Rewrite System Revisited, Corrigendum to our paper: How Expressions Can Code for Automata, Subset construction complexity for homogeneous automata, position automata and ZPC-structures, Kleene Theorems for Product Systems, From $$\omega $$-Regular Expressions to Büchi Automata via Partial Derivatives, From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity, On Average Behaviour of Regular Expressions in Strong Star Normal Form, Partial derivatives of regular expressions over alphabet-invariant and user-defined labels, On the size of partial derivatives and the word membership problem, Partial Derivative Automata Formalized in Coq, Compact representations of automata for regular expression matching, Operational semantics with semicommutations, An Efficient Algorithm for the Construction of the Equation Tree Automaton, From Tree Automata to Rational Tree Expressions, Regular expression order-sorted unification and matching, FROM THE $\mathcal{ZPC}$ STRUCTURE OF A REGULAR EXPRESSION TO ITS FOLLOW AUTOMATON, Position Automaton Construction for Regular Expressions with Intersection, Fast equation automaton computation, Hedge Pattern Partial Derivative, Construction of tree automata from regular expressions, ANTIMIROV AND MOSSES'S REWRITE SYSTEM REVISITED, On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection, Derived-Term Automata of Multitape Rational Expressions, Derivative-Based Diagnosis of Regular Expression Ambiguity, Derivatives for Enhanced Regular Expressions, Automata and rational expressions, Descriptional complexity of regular languages, An efficient null-free procedure for deciding regular language membership, Inclusion Test Algorithms for One-Unambiguous Regular Expressions, Unnamed Item, A formally verified, optimized monitor for metric first-order dynamic logic, Partial derivative automaton by compressing regular expressions, The Bottom-Up Position Tree Automaton and the Father Automaton, Canonical derivatives, partial derivatives and finite automaton constructions., Deciding Kleene algebra terms equivalence in Coq, Bottom-Up derivatives of tree expressions, A goal-directed decision procedure for hybrid PDL, A formalisation of the Myhill-Nerode theorem based on regular expressions, Kleene Theorems for Synchronous Products with Matching, Computing with relational machines, Operads, quasiorders, and regular languages, On the hierarchy of generalizations of one-unambiguous regular languages
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- From regular expressions to deterministic automata
- On equations for regular languages, finite automata, and sequential networks
- Rewriting extended regular expressions
- Undecidability of ground reducibility for word rewriting systems with variables
- Complexity of matching problems
- Order-sorted algebra. I: Equational deduction for multiple inheritance, overloading, exceptions and partial operations
- Regular expressions into finite automata
- From regular expressions to DFA's using compressed NFA's
- A taxonomy of sublinear multiple keyword pattern matching algorithms
- Linear Automaton Transformations
- THE ABSTRACT THEORY OF AUTOMATA
- DIFFERENTIATION OF K-RATIONAL EXPRESSIONS
- Partial derivatives of regular expressions and finite automata constructions
- A Procedure for Checking Equality of Regular Expressions
- Programming Techniques: Regular expression search algorithm
- Derivatives of Regular Expressions
- The Invalidity of Markoff's Schema
