Exact complexity of problems of incompletely specified automata

DOI10.1007/BF02127799zbMath0860.68070MaRDI QIDQ1817068

Nadia Creignou

Publication date: 1 December 1996

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

reduction of incompletely specified automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (1)

Sorting, linear time and the satisfiability problem

Cites Work

• Unnamed Item
• Unnamed Item
• The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
• Minimal coverings for incompletely specified sequential machines
• Sorting, linear time and the satisfiability problem
• A Nontrivial Lower Bound for an NP Problem on Automata
• Linear time transformations between combinatorial problems
• Complexity of automaton identification from given data
• Linear Time Algorithms and NP-Complete Problems
• State Reduction in Incompletely Specified Finite-State Machines

This page was built for publication: Exact complexity of problems of incompletely specified automata