Power of counting by nonuniform families of polynomial-size finite automata
From MaRDI portal
Publication:6546609
DOI10.1007/978-3-031-43587-4_30MaRDI QIDQ6546609
Publication date: 29 May 2024
closure propertiescounting functionscounting complexity classesnonuniform polynomial state complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Immunity and pseudorandomness of context-free languages
- Pseudorandom generators against advised context-free languages
- Theory of one-tape linear-time Turing machines
- Space-bounded hierarchies and probabilistic computations
- A very hard log-space counting class
- Relative complexity of checking and evaluating
- Gap-definable counting classes
- Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits
- Two-way automata versus logarithmic space
- Relativizations of nonuniform quantum finite automata families
- Two-way automata characterizations of L/poly versus NL
- A complexity theory for feasible closure properties
- THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA
- PP is as Hard as the Polynomial-Time Hierarchy
- Size Complexity of Two-Way Finite Automata
- The Complexity of Enumeration and Reliability Problems
- Relationships among $PL$, $\#L$, and the determinant
- 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
- Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice
- Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata
Related Items (1)
This page was built for publication: Power of counting by nonuniform families of polynomial-size finite automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6546609)
