Partial derivatives of regular expressions and finite automaton constructions
From MaRDI portal
Publication:672142
DOI10.1016/0304-3975(95)00182-4zbMATH Open0872.68120OpenAlexW2094985106MaRDI QIDQ672142FDOQ672142
Authors: Valentin Antimirov 
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
Recommendations
- Partial derivatives of regular expressions and finite automata constructions
- Canonical derivatives, partial derivatives and finite automaton constructions.
- Partial derivatives of an extended regular expression
- From regular expressions to deterministic automata
- scientific article; zbMATH DE number 1773077
non-deterministic finite automataalgorithm for turning regular expressions into NFA'sBrzozowski's algorithmpartial derivative of a regular expression
Cites Work
- THE ABSTRACT THEORY OF AUTOMATA
- Title not available (Why is that?)
- Derivatives of Regular Expressions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Order-sorted algebra. I: Equational deduction for multiple inheritance, overloading, exceptions and partial operations
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On equations for regular languages, finite automata, and sequential networks
- Complexity of matching problems
- Programming Techniques: Regular expression search algorithm
- Linear Automaton Transformations
- Regular expressions into finite automata
- From regular expressions to deterministic automata
- Title not available (Why is that?)
- From regular expressions to DFA's using compressed NFA's
- A taxonomy of sublinear multiple keyword pattern matching algorithms
- Title not available (Why is that?)
- DIFFERENTIATION OF K-RATIONAL EXPRESSIONS
- Title not available (Why is that?)
- Partial derivatives of regular expressions and finite automata constructions
- A Procedure for Checking Equality of Regular Expressions
- The Invalidity of Markoff's Schema
- Rewriting extended regular expressions
- Undecidability of ground reducibility for word rewriting systems with variables
Cited In (only showing first 100 items - show all)
- Simplifying regular expressions further
- Operads, quasiorders, and regular languages
- The complexity of regular(-like) expressions
- Inclusion Test Algorithms for One-Unambiguous Regular Expressions
- Canonical derivatives, partial derivatives and finite automaton constructions.
- A formalisation of the Myhill-Nerode theorem based on regular expressions
- Computing with relational machines
- Multi-tilde-bar expressions and their automata
- On the average state complexity of partial derivative automata: an analytic combinatorics approach
- Title not available (Why is that?)
- Derivatives for Enhanced Regular Expressions
- Almost event-rate independent monitoring
- Partial derivative automata formalized in Coq
- Derivatives of rational expressions and related theorems.
- How expressions can code for automata
- Algorithms for Kleene algebra with converse
- Implementation and Application of Automata
- Deciding Synchronous Kleene Algebra with Derivatives
- Operational semantics with semicommutations
- Compact representations of automata for regular expression matching
- Regular expression order-sorted unification and matching
- Reducing NFAs by invariant equivalences.
- Regular-expression derivatives re-examined
- Rational and Recognisable Power Series
- A Decision Procedure for Regular Membership and Length Constraints over Unbounded Strings
- Construction of fuzzy automata from fuzzy regular expressions
- Derivatives of rational expressions with multiplicity
- On the size of partial derivatives and the word membership problem
- From $$\omega $$-Regular Expressions to Büchi Automata via Partial Derivatives
- FROM REGULAR WEIGHTED EXPRESSIONS TO FINITE AUTOMATA
- A mesh of automata
- Bottom-Up derivatives of tree expressions
- On Average Behaviour of Regular Expressions in Strong Star Normal Form
- Manipulation of regular expressions using derivatives: an overview
- Postfix automata
- Verified decision procedures for MSO on words based on derivatives of regular expressions
- From regular expressions to finite automata∗
- Location based automata for expressions with shuffle
- A formally verified, optimized monitor for metric first-order dynamic logic
- An efficient null-free procedure for deciding regular language membership
- Derivative-Based Diagnosis of Regular Expression Ambiguity
- From regular expressions to smaller NFAs
- Completeness and the finite model property for Kleene algebra, reconsidered
- Derivatives and partial derivatives for regular shuffle expressions
- On the computation of quotients and factors of regular languages
- Deciding Kleene algebra terms equivalence in Coq
- From finite automata to regular expressions and back -- a summary on descriptional complexity
- A goal-directed decision procedure for hybrid PDL
- FROM THE $\mathcal{ZPC}$ STRUCTURE OF A REGULAR EXPRESSION TO ITS FOLLOW AUTOMATON
- Extended to multi-tilde-bar regular expressions and efficient finite automata constructions
- From regular expressions to deterministic automata
- Derived-Term Automata of Multitape Rational Expressions
- On the Average State Complexity of Partial Derivative Transducers
- Automata and rational expressions
- Descriptional complexity of regular languages
- Partial Derivatives for Context-Free Languages
- Extension of Brzozowski's derivation calculus of rational expressions to series over the free partially commutative monoids
- Fast equation automaton computation
- Position Automaton Construction for Regular Expressions with Intersection
- ANTIMIROV AND MOSSES'S REWRITE SYSTEM REVISITED
- Automata for regular expressions with shuffle
- CLP(H):Constraint logic programming for hedges
- Derivatives of regular expressions and an application
- From Mirkin's prebases to Antimirov's word partial derivatives
- On the average size of Glushkov and partial derivative automata
- Follow automata.
- FROM C-CONTINUATIONS TO NEW QUADRATIC ALGORITHMS FOR AUTOMATON SYNTHESIS
- Title not available (Why is that?)
- Partial derivatives of an extended regular expression
- Partial derivative automaton by compressing regular expressions
- Space-Efficient Representations for Glushkov Automata
- Left is Better Than Right for Reducing Nondeterminism of NFAs
- Corrigendum to our paper: How Expressions Can Code for Automata
- From Tree Automata to Rational Tree Expressions
- An Efficient Algorithm for the Construction of the Equation Tree Automaton
- Title not available (Why is that?)
- Construction of state diagram of regular expressions using derivatives
- The Bottom-Up Position Tree Automaton and the Father Automaton
- Derivatives and Finite Automata of Expressions in Star Normal Form
- Approximate regular expressions and their derivatives
- Derivatives of approximate regular expressions
- Title not available (Why is that?)
- Construction of tree automata from regular expressions
- Reordering Derivatives of Trace Closures of Regular Languages.
- Partial derivatives of regular expressions over alphabet-invariant and user-defined labels
- A Coinductive Reformulation of Milner's Proof System for Regular Expressions Modulo Bisimilarity
- Title not available (Why is that?)
- Kleene Theorems for Synchronous Products with Matching
- Verification and enforcement of access control policies
- Construction of Tree Automata from Regular Expressions
- Algorithms for checking intersection non-emptiness of regular expressions
- Hedge Pattern Partial Derivative
- On the hierarchy of generalizations of one-unambiguous regular languages
- Efficient weighted expressions conversion
- Prefix and Right-Partial Derivative Automata
- Location automata for regular expressions with shuffle and intersection
- Two-sided derivatives for regular expressions and for hairpin expressions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Partial derivative and position bisimilarity automata
Uses Software
This page was built for publication: Partial derivatives of regular expressions and finite automaton constructions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672142)
