ON THE AVERAGE STATE COMPLEXITY OF PARTIAL DERIVATIVE AUTOMATA: AN ANALYTIC COMBINATORICS APPROACH

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)

zbMATH Keywords

regular expressions; regular languages; average case analysis; partial derivatives; analytic combinatorics; conversion between regular expressions and nondeterministic finite automata

Mathematics Subject Classification ID

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

• FAdo
• GUItar

Cites Work

• Partial derivatives of regular expressions and finite automaton constructions
• Generating words in a context-free language uniformly at random
• Follow automata.
• Canonical derivatives, partial derivatives and finite automaton constructions.
• Derivatives of Regular Expressions