Exact complexity of problems of incompletely specified automata
From MaRDI portal
Recommendations
- Complexity of some problems from the theory of automata
- Complexity of exclusive nondeterministic finite automata
- scientific article; zbMATH DE number 4041268
- Computational complexity of decision problems on self-verifying finite automata
- Complexity of preimage problems for deterministic finite automata
- Descriptional and Computational Complexity of Finite Automata
- scientific article; zbMATH DE number 1189125
- Intractability of decision problems for finite-memory automata
- DNA Computing
- On the computational complexity of P automata
Cites work
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A Nontrivial Lower Bound for an NP Problem on Automata
- Complexity of automaton identification from given data
- Linear Time Algorithms and NP-Complete Problems
- Linear time transformations between combinatorial problems
- Minimal coverings for incompletely specified sequential machines
- Sorting, linear time and the satisfiability problem
- State Reduction in Incompletely Specified Finite-State Machines
- The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
Cited in
(8)- scientific article; zbMATH DE number 1189125 (Why is no real title available?)
- Computational complexity of decision problems on self-verifying finite automata
- scientific article; zbMATH DE number 7298596 (Why is no real title available?)
- scientific article; zbMATH DE number 826075 (Why is no real title available?)
- Sorting, linear time and the satisfiability problem
- Complexity of some problems from the theory of automata
- The Complexity of Mean-Payoff Automaton Expression
- scientific article; zbMATH DE number 4026835 (Why is no real title available?)
This page was built for publication: Exact complexity of problems of incompletely specified automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1817068)
