ON THE AVERAGE STATE COMPLEXITY OF PARTIAL DERIVATIVE AUTOMATA: AN ANALYTIC COMBINATORICS APPROACH
From MaRDI portal
Publication:2909097
DOI10.1142/S0129054111008908zbMath1252.68166MaRDI QIDQ2909097
António Machiavelo, Sabine Broda, Nelma Moreira, Rogério Reis
Publication date: 29 August 2012
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
regular expressions; regular languages; average case analysis; partial derivatives; analytic combinatorics; conversion between regular expressions and nondeterministic finite automata
68Q45: Formal languages and automata
Related Items
ON THE AVERAGE SIZE OF GLUSHKOV AND PARTIAL DERIVATIVE AUTOMATA, Unnamed Item, On Average Behaviour of Regular Expressions in Strong Star Normal Form, Partial derivatives of regular expressions over alphabet-invariant and user-defined labels, Random Regular Expression Over Huge Alphabets, Automata for regular expressions with shuffle, On the size of partial derivatives and the word membership problem, Partial derivative automaton by compressing regular expressions, Manipulation of regular expressions using derivatives: an overview, A hitchhiker's guide to descriptional complexity through analytic combinatorics, On the average complexity of partial derivative transducers, On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection, Prefix and Right-Partial Derivative Automata, On the Average State Complexity of Partial Derivative Transducers
Uses Software
Cites Work