Power of counting by nonuniform families of polynomial-size finite automata
From MaRDI portal
(Redirected from Publication:6546609)
Power of counting by nonuniform families of polynomial-size finite automata (scientific article; zbMATH DE number 7856035)
Power of counting by nonuniform families of polynomial-size finite automata (scientific article; zbMATH DE number 7856035)
Cites work
- A complexity theory for feasible closure properties
- A very hard log-space counting class
- Gap-definable counting classes
- scientific article; zbMATH DE number 3568031 (Why is no real title available?)
- Immunity and pseudorandomness of context-free languages
- Minicomplexity
- Nondeterminism and the size of two way finite automata
- PP is as Hard as the Polynomial-Time Hierarchy
- Pseudorandom generators against advised context-free languages
- Relationships among $PL$, $\#L$, and the determinant
- Relative complexity of checking and evaluating
- Relativizations of nonuniform quantum finite automata families
- Size Complexity of Two-Way Finite Automata
- Space-bounded hierarchies and probabilistic computations
- The Complexity of Enumeration and Reliability Problems
- THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA
- Theory of one-tape linear-time Turing machines
- Two-way automata characterizations of L/poly versus NL
- Two-way automata versus logarithmic space
- Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata
- Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits
Cited in
(2)
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)
