Weak cardinality theorems

DOI10.2178/JSL/1122038917MaRDI QIDQ5718691zbMATH OpenOpenAlexFDO

Authors 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

cardinality theoremfinite automatalogical structuresTuring machines

Mathematics Subject Classification ID

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

Recommendations

• Weak cardinality theorems for first-order logic (extended abstract)
• scientific article; zbMATH DE number 1929974
• A cardinality version of Beigel's nonspeedup theorem
• A proof of Beigel's cardinality conjecture
• Constructing sets of functions which have a givenF-cardinality

Cites work

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

Cited in

(8)

• Weakly measurable cardinals
• Weakly compact cardinals in models of set theory
• Constructing sets of functions which have a givenF-cardinality
• Weak Covering at Large Cardinals
• scientific article; zbMATH DE number 1929974 (Why is no real title available?)
• A cardinality version of Beigel's nonspeedup theorem
• scientific article; zbMATH DE number 806742 (Why is no real title available?)
• Weak cardinality theorems for first-order logic (extended abstract)

This page was built for publication: Weak cardinality theorems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5718691)