Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata
From MaRDI portal
Publication:6173104
DOI10.1007/978-3-031-19135-0_6OpenAlexW4312258751MaRDI QIDQ6173104
Publication date: 21 July 2023
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-031-19135-0_6
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Turing machines that take advice
- Relative complexity of checking and evaluating
- On the power of unambiguity in log-space
- Two-way automata versus logarithmic space
- Relativizations of nonuniform quantum finite automata families
- Two-way automata characterizations of L/poly versus NL
- Directed Planar Reachability Is in Unambiguous Log-Space
- Size Complexity of Two-Way Finite Automata
- P-Printable Sets
- Making Nondeterminism Unambiguous
- Nondeterminism and the size of two way finite automata
- State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis
- An introduction to Kolmogorov complexity and its applications
- Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice
This page was built for publication: Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata
