Average case analysis of Brzozowski's algorithm

DOI10.1142/S0129054116400025zbMATH Open1338.68143OpenAlexW2345697090MaRDI QIDQ2814833FDOQ2814833

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

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)\)

zbMATH Keywords

average-case analysisautomata minimizationBrzozowski's algorithm

Mathematics Subject Classification ID

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

Cites Work

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

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)