A Multivariate Analysis of Some DFA Problems

DOI10.1007/978-3-642-37064-9_25zbMath1377.68109OpenAlexW70941151MaRDI QIDQ4910465

Pinar Heggernes, Henning Fernau, Yngve Villanger

Publication date: 18 March 2013

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-37064-9_25

zbMATH Keywords

deterministic finite automatasynchronizing wordconsistency problemNP-hard decision problems

Mathematics Subject Classification ID

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

Related Items (3)

Complexity of road coloring with prescribed reset words ⋮ Regular inference as vertex coloring ⋮ A multi-parameter analysis of hard problems on deterministic finite automata

This page was built for publication: A Multivariate Analysis of Some DFA Problems