ON THE AVERAGE SIZE OF GLUSHKOV AND PARTIAL DERIVATIVE AUTOMATA
From MaRDI portal
Publication:4902888
DOI10.1142/S0129054112400400zbMath1262.68085MaRDI QIDQ4902888
Rogério Reis, Nelma Moreira, António Machiavelo, Sabine Broda
Publication date: 18 January 2013
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
regular expressionsregular languagesaverage case analysispartial derivativesanalytic combinatoricsconversion between regular expressions and nondeterministic finite automata
Related Items
Prefix and Right-Partial Derivative Automata ⋮ Manipulation of regular expressions using derivatives: an overview ⋮ Deciding Synchronous Kleene Algebra with Derivatives ⋮ Random Regular Expression Over Huge Alphabets ⋮ Average complexity of partial derivatives for synchronised shuffle expressions ⋮ Automata for regular expressions with shuffle ⋮ A hitchhiker's guide to descriptional complexity through analytic combinatorics ⋮ Unnamed Item ⋮ A mesh of automata ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ On Average Behaviour of Regular Expressions in Strong Star Normal Form ⋮ On the size of partial derivatives and the word membership problem ⋮ On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection ⋮ On the uniform distribution of regular expressions ⋮ Partial derivative automaton by compressing regular expressions ⋮ Analysis of an efficient reduction algorithm for random regular expressions based on universality detection
Cites Work
- From regular expressions to deterministic automata
- Partial derivatives of regular expressions and finite automaton constructions
- Regular expressions into finite automata
- Canonical derivatives, partial derivatives and finite automaton constructions.
- ON THE AVERAGE STATE COMPLEXITY OF PARTIAL DERIVATIVE AUTOMATA: AN ANALYTIC COMBINATORICS APPROACH
- THE ABSTRACT THEORY OF AUTOMATA
- Derivatives of Regular Expressions
