Power of counting by nonuniform families of polynomial-size finite automata

DOI10.1007/978-3-031-43587-4_30MaRDI QIDQ6546609zbMATH OpenFDO

Authors Tomoyuki Yamakami

Publication date 29 May 2024

zbMATH Keywords

closure propertiescounting functionscounting complexity classesnonuniform polynomial state complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 3568031 (Why is no real title available?)
• A complexity theory for feasible closure properties
• A very hard log-space counting class
• Gap-definable counting classes
• 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 ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA
• The Complexity of Enumeration and Reliability Problems
• 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

(1)

• Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and the effects of multiple counters

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)