The Tractability Frontier for NFA Minimization

DOI10.1007/978-3-540-70583-3_3zbMath1155.68415OpenAlexW3023852645MaRDI QIDQ3520301

Wim Martens, Henrik Björklund

Publication date: 19 August 2008

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-70583-3_3

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Generating, sampling and counting subclasses of regular tree languages ⋮ The tractability frontier for NFA minimization ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Descriptional and Computational Complexity of Finite Automata

This page was built for publication: The Tractability Frontier for NFA Minimization