Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata

DOI10.1007/978-3-642-38771-5_17zbMath1381.68113OpenAlexW35268004MaRDI QIDQ5300839

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)

Related Items (6)

Random Deterministic Automata ⋮ A hitchhiker's guide to descriptional complexity through analytic combinatorics ⋮ Theory of átomata ⋮ Standard Sturmian words and automata minimization algorithms ⋮ Minimisation of automata ⋮ Diameter and stationary distribution of random \(r\)-out digraphs

This page was built for publication: Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata