Brzozowski algorithm is generically super-polynomial for deterministic automata

DOI10.1007/978-3-642-38771-5_17MaRDI QIDQ5300839zbMATH OpenOpenAlexFDO

Authors Sven De Felice, Cyril Nicaud

Publication date 28 June 2013

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-38771-5_17

Mathematics Subject Classification ID

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

Recommendations

• On the average complexity of Brzozowski's algorithm for deterministic automata with a small number of final states
• Average case analysis of Brzozowski's algorithm
• Brzozowski's minimization algorithm -- more robust than expected (extended abstract)
• Random deterministic automata
• A polynomial double reversal minimization algorithm for deterministic finite automata

Cited in

(11)

• Minimisation of automata
• A hitchhiker's guide to descriptional complexity through analytic combinatorics
• Theory of átomata
• Average case analysis of Brzozowski's algorithm
• Brzozowski's algorithm (co)algebraically
• On the average complexity of Brzozowski's algorithm for deterministic automata with a small number of final states
• Random deterministic automata
• Standard Sturmian words and automata minimization algorithms
• Brzozowski's minimization algorithm -- more robust than expected (extended abstract)
• Random deterministic automata with one added transition
• Diameter and stationary distribution of random r-out digraphs

This page was built for publication: Brzozowski algorithm is generically super-polynomial for deterministic automata

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