On the average size of Glushkov and partial derivative automata

DOI10.1142/S0129054112400400MaRDI QIDQ4902888zbMATH OpenFDO

Authors Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis

Publication date 18 January 2013

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054112400400

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

The Average Transition Complexity of Glushkov and Partial Derivative Automata
On the Average Number of States of Partial Derivative Automata
On the average state complexity of partial derivative automata: an analytic combinatorics approach
On the Average Size of Glushkov’s Automata
Average analysis of Glushkov automata under a BST-like model

Cites work

Canonical derivatives, partial derivatives and finite automaton constructions.
Derivatives of Regular Expressions
From regular expressions to deterministic automata
On the average state complexity of partial derivative automata: an analytic combinatorics approach
Partial derivatives of regular expressions and finite automaton constructions
Regular expressions into finite automata
THE ABSTRACT THEORY OF AUTOMATA

Cited in

(30)

Automata for regular expressions with shuffle
On the size of partial derivatives and the word membership problem
On the uniform distribution of regular expressions
Partial derivative automaton by compressing regular expressions
Analysis of an efficient reduction algorithm for random regular expressions based on universality detection
Manipulation of regular expressions using derivatives: an overview
A mesh of automata
A hitchhiker's guide to descriptional complexity through analytic combinatorics
On the average complexity of partial derivative transducers
From finite automata to regular expressions and back -- a summary on descriptional complexity
On the state complexity of partial derivative automata for regular expressions with intersection
On the average size of Glushkov and equation automata for KAT expressions
Average analysis of Glushkov automata under a BST-like model
On the average state complexity of partial derivative automata: an analytic combinatorics approach
Deciding synchronous Kleene algebra with derivatives
Prefix and Right-Partial Derivative Automata
On the average state complexity of partial derivative transducers
On the Average Number of States of Partial Derivative Automata
On the Average Size of Glushkov’s Automata
On the average minimal prefix-length of the generalized semi-Dycklanguage
On the average complexity of partial derivative automata for semi-extended expressions
The prefix automaton
The Average Transition Complexity of Glushkov and Partial Derivative Automata
On average behaviour of regular expressions in strong star normal form
Random Regular Expression Over Huge Alphabets
Average complexity of partial derivatives for synchronised shuffle expressions
Average state complexity of partial derivative automata for synchronised shuffles
Automata for synchronised shuffle on backbones
Regular expressions avoiding absorbing patterns and the significance of uniform distribution
Compressed structures for partial derivative automata constructions

This page was built for publication: On the average size of Glushkov and partial derivative automata

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