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

DOI10.1142/S0129054111008908zbMATH Open1252.68166MaRDI QIDQ2909097FDOQ2909097

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)

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

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)

Cites Work

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

Cited In (17)

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

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)