A multivariate analysis of some DFA problems

DOI10.1007/978-3-642-37064-9_25MaRDI QIDQ4910465zbMATH OpenOpenAlexFDO

Authors Henning Fernau, Pinar Heggernes, 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

consistency problemdeterministic finite automataNP-hard decision problemssynchronizing word

Mathematics Subject Classification ID

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

Recommendations

• A multi-parameter analysis of hard problems on deterministic finite automata
• Synchronizing words and monoid factorization: a parameterized perspective
• Synchronizing series-parallel deterministic finite automata with loops and related problems
• Minimal NFA Problems are Hard
• scientific article; zbMATH DE number 176769

Cited in

(8)

• Oblivious DFA evaluation on joint input and its applications
• Synchronizing words and monoid factorization: a parameterized perspective
• A multi-parameter analysis of hard problems on deterministic finite automata
• Regular inference as vertex coloring
• scientific article; zbMATH DE number 1927179 (Why is no real title available?)
• Synchronizing words and monoid factorization, yielding a new parameterized complexity class?
• A Brief Introduction to DFA-Based Multiscale Analysis
• Some New Features and Algorithms for the Study of DFA

This page was built for publication: A multivariate analysis of some DFA problems

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