On the average state complexity of partial derivative automata: an analytic combinatorics approach
From MaRDI portal
Publication:2909097
DOI10.1142/S0129054111008908zbMATH Open1252.68166MaRDI QIDQ2909097FDOQ2909097
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)
partial derivativesregular languagesregular expressionsanalytic combinatoricsaverage case analysisconversion between regular expressions and nondeterministic finite automata
Cites Work
Cited In (16)
- A hitchhiker's guide to descriptional complexity through analytic combinatorics
- Title not available (Why is that?)
- Partial derivatives of regular expressions over alphabet-invariant and user-defined labels
- On the Average Number of States of Partial Derivative Automata
- Prefix and Right-Partial Derivative Automata
- ON THE AVERAGE SIZE OF GLUSHKOV AND PARTIAL DERIVATIVE AUTOMATA
- On the size of partial derivatives and the word membership problem
- On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection
- On Average Behaviour of Regular Expressions in Strong Star Normal Form
- Manipulation of regular expressions using derivatives: an overview
- The Average Transition Complexity of Glushkov and Partial Derivative Automata
- On the Average State Complexity of Partial Derivative Transducers
- Automata for regular expressions with shuffle
- Random Regular Expression Over Huge Alphabets
- On the average complexity of partial derivative transducers
- Partial derivative automaton by compressing regular expressions
Uses Software
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)
