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

DOI10.1007/978-3-031-43587-4_30MaRDI QIDQ6546609FDOQ6546609

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

• Space-bounded hierarchies and probabilistic computations
• The Complexity of Enumeration and Reliability Problems
• PP is as Hard as the Polynomial-Time Hierarchy
• Relationships among $PL$, $\#L$, and the determinant
• Relative complexity of checking and evaluating
• A very hard log-space counting class
• Size Complexity of Two-Way Finite Automata
• Nondeterminism and the size of two way finite automata
• Gap-definable counting classes
• A complexity theory for feasible closure properties
• Title not available (Why is that?)
• Immunity and pseudorandomness of context-free languages
• Pseudorandom generators against advised context-free languages
• Theory of one-tape linear-time Turing machines
• Two-way automata versus logarithmic space
• Minicomplexity
• Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits
• Relativizations of nonuniform quantum finite automata families
• THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA
• Two-way automata characterizations of L/poly versus NL
• Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata

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)