Weak cardinality theorems

DOI10.2178/jsl/1122038917zbMath1092.03020OpenAlexW2072890682MaRDI QIDQ5718691

Till Tantau

Publication date: 16 January 2006

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2178/jsl/1122038917

zbMATH Keywords

Turing machinesfinite automatacardinality theoremlogical structures

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong exponential hierarchy collapses
• Comparing verboseness for finite automata and Turing machines
• \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Bounded queries in recursion theory
• Enumerative counting is hard
• A structural property of regular frequency computations.
• Nondeterministic Space is Closed under Complementation
• Frequency computations and the cardinality theorem
• A Downward Collapse within the Polynomial Hierarchy
• Effective Search Problems
• A cardinality version of Beigel's nonspeedup theorem
• Concatenation as a basis for arithmetic

This page was built for publication: Weak cardinality theorems