From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity
From MaRDI portal
Publication:2800411
DOI10.1142/S0129054115400110zbMath1405.68165arXiv1405.5594MaRDI QIDQ2800411
Publication date: 15 April 2016
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1405.5594
Related Items
State complexity of permutation on finite languages over a binary alphabet, Manipulation of regular expressions using derivatives: an overview, Regularity of k-Abelian Equivalence Classes of Fixed Cardinality, A mesh of automata, A deterministic parsing algorithm for ambiguous regular expressions, Natural strategic ability, Regular expression length via arithmetic formula complexity, A logic for document spanners, Structural properties of NFAs and growth rates of nondeterminism measures
Cites Work
- Descriptional and computational complexity of finite automata -- a survey
- From regular expressions to deterministic automata
- Partial derivatives of regular expressions and finite automaton constructions
- Introducing VAUCANSON
- From regular expressions to smaller NFAs
- Obtaining shorter regular expressions from finite-state automata
- On measuring nondeterminism in regular languages
- Generalizations of 1-deterministic regular languages
- Succinctness of regular expressions with interleaving, intersection and counting
- Unary finite automata vs. arithmetic progressions
- A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression
- The complexity of restricted regular expressions and the synthesis problem for finite automata
- Finite automata and unary languages
- Algorithms for determining relative star height and star height
- On the relation between ambiguity and nondeterminism in finite automata
- Inherently nonplanar automata
- Complexity measures for regular expressions
- On finite automata with limited nondeterminism
- Regular expressions into finite automata
- Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions
- A characterization of Thompson digraphs.
- Follow automata.
- Characterization of Glushkov automata
- The inclusion problem for regular expressions
- Canonical derivatives, partial derivatives and finite automaton constructions.
- Communication complexity method for measuring nondeterminism in finite automata
- A hitchhiker's guide to descriptional complexity through analytic combinatorics
- Transition graphs and the star-height of regular events
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
- THE ABSTRACT THEORY OF AUTOMATA
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
- Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
- ON THE AVERAGE SIZE OF GLUSHKOV AND PARTIAL DERIVATIVE AUTOMATA
- PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA
- NORMALIZED EXPRESSIONS AND FINITE AUTOMATA
- Programming Techniques: Regular expression search algorithm
- The loop complexity of pure-group events
- Design of Sequential Machines from Their Regular Expressions
- Ambiguity in Graphs and Expressions
- Derivatives of Regular Expressions
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
- One-unambiguous regular languages
- Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
