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 expressionsregular languagesaverage case analysispartial derivativesanalytic combinatoricsconversion between regular expressions and nondeterministic finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (14)

Prefix and Right-Partial Derivative Automata ⋮ Manipulation of regular expressions using derivatives: an overview ⋮ Random Regular Expression Over Huge Alphabets ⋮ Automata for regular expressions with shuffle ⋮ On the average complexity of partial derivative transducers ⋮ A hitchhiker's guide to descriptional complexity through analytic combinatorics ⋮ On the Average State Complexity of Partial Derivative Transducers ⋮ 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 ⋮ On the size of partial derivatives and the word membership problem ⋮ On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection ⋮ Partial derivative automaton by compressing regular expressions

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

This page was built for publication: ON THE AVERAGE STATE COMPLEXITY OF PARTIAL DERIVATIVE AUTOMATA: AN ANALYTIC COMBINATORICS APPROACH