On the average state complexity of partial derivative automata: an analytic combinatorics approach

DOI10.1142/S0129054111008908MaRDI QIDQ2909097zbMATHFDO

Authors Sabine Broda, António Machiavelo, 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

partial derivativesregular languagesregular expressionsanalytic combinatoricsaverage case analysisconversion between regular expressions and nondeterministic finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the Average Number of States of Partial Derivative Automata
• On the average size of Glushkov and partial derivative automata
• The Average Transition Complexity of Glushkov and Partial Derivative Automata
• On the state complexity of partial derivative automata for regular expressions with intersection
• On the size of partial derivatives and the word membership problem

Cites work

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

Cited in

(17)

• Partial derivative automaton by compressing regular expressions
• On the state complexity of partial derivative automata for regular expressions with intersection
• On the size of partial derivatives and the word membership problem
• On the Average Number of States of Partial Derivative Automata
• The prefix automaton
• On the average state complexity of partial derivative transducers
• Random Regular Expression Over Huge Alphabets
• Partial derivatives of regular expressions over alphabet-invariant and user-defined labels
• The Average Transition Complexity of Glushkov and Partial Derivative Automata
• Prefix and Right-Partial Derivative Automata
• On average behaviour of regular expressions in strong star normal form
• On the average size of Glushkov and partial derivative automata
• On the average complexity of partial derivative automata for semi-extended expressions
• On the average complexity of partial derivative transducers
• A hitchhiker's guide to descriptional complexity through analytic combinatorics
• Automata for regular expressions with shuffle
• Manipulation of regular expressions using derivatives: an overview

Describes a project that uses

Uses Software

• FAdo
• GUItar

This page was built for publication: On the average state complexity of partial derivative automata: an analytic combinatorics approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2909097)