On the Average Size of Glushkov’s Automata

DOI10.1007/978-3-642-00982-2_53zbMath1234.68232OpenAlexW1585835864MaRDI QIDQ3618617

Cyril Nicaud

Publication date: 2 April 2009

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-00982-2_53

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (20)

On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations ⋮ Prefix and Right-Partial Derivative Automata ⋮ Manipulation of regular expressions using derivatives: an overview ⋮ How to settle the ReDoS problem: back to the classical automata theory ⋮ On the Uniform Random Generation of Non Deterministic Automata Up to Isomorphism ⋮ Random Regular Expression Over Huge Alphabets ⋮ The effects of semantic simplifications on random \textit{BST}-like expression-trees ⋮ Simplifications of Uniform Expressions Specified by Systems ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On Average Behaviour of Regular Expressions in Strong Star Normal Form ⋮ On the size of partial derivatives and the word membership problem ⋮ Enumerating regular expressions and their languages ⋮ On the uniform distribution of regular expressions ⋮ Partial derivative automaton by compressing regular expressions ⋮ The Bottom-Up Position Tree Automaton and the Father Automaton

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algebraic simplification in computer algebra: an analysis of bottom-up algorithms
• The average height of binary trees and other simple trees
• THE ABSTRACT THEORY OF AUTOMATA
• Computingϵ-Free NFA from Regular Expressions inO(nlog²(n)) Time
• Implementation and Application of Automata
• Implementation and Application of Automata
• Implementation and Application of Automata

This page was built for publication: On the Average Size of Glushkov’s Automata