A multi-parameter analysis of hard problems on deterministic finite automata

DOI10.1016/j.jcss.2014.12.027zbMath1320.68090MaRDI QIDQ2256724

Henning Fernau, Pinar Heggernes, Yngve Villanger

Publication date: 20 February 2015

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2014.12.027

zbMATH Keywords

deterministic finite automata; synchronizing word; consistency problem; NP-hard decision problems

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Uses Software

• COMPAS