Average case analysis of Brzozowski's algorithm

DOI10.1142/S0129054116400025MaRDI QIDQ2814833zbMATH OpenOpenAlexFDO

Authors Sven De Felice, Cyril Nicaud

Publication date 23 June 2016

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

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

zbMATH Keywords

average-case analysisautomata minimizationBrzozowski's algorithm

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the average complexity of Brzozowski's algorithm for deterministic automata with a small number of final states
• Brzozowski algorithm is generically super-polynomial for deterministic automata
• Average case analysis of Moore's state minimization algorithm
• On the average complexity of Moore's state minimization algorithm
• The average complexity of Moore's state minimization algorithm is \(\mathcal O( n \log\log n)\)

Cites work

• Average case analysis of Moore's state minimization algorithm
• Average complexity of Moore's and Hopcroft's algorithms

Cited in

(8)

• Brzozowski algorithm is generically super-polynomial for deterministic automata
• A hitchhiker's guide to descriptional complexity through analytic combinatorics
• Average case analysis of Moore's state minimization algorithm
• Average-case analysis of some plurality algorithms
• Minimisation of automata
• Average-case analysis of the double description method and the beneath-beyond algorithm
• On the average complexity of Brzozowski's algorithm for deterministic automata with a small number of final states
• Random deterministic automata

This page was built for publication: Average case analysis of Brzozowski's algorithm

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