Incompleteness Theorems, Large Cardinals, and Automata Over Finite Words

DOI10.1142/S012905411950014XzbMath1459.03056MaRDI QIDQ5384126

Olivier Finkel

Publication date: 21 June 2019

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

independenceautomatacontext-free grammarslarge cardinalsPeano arithmeticformal languageslogic in computer sciencePost correspondence problemmodels of set theoryincompleteness theoremsweighted automatoninaccessible cardinalsfinite words\(2\)-tape automatonfinitely generated matrix subsemigroups of \(\mathbb Z^{3 \times 3}\)

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Large cardinals (03E55) Gödel numberings and issues of incompleteness (03F40)

Cites Work

• On Gödel incompleteness and finite combinatorics
• Independence results about context-free languages and lower bounds
• How recent work in mathematical logic relates to the foundations of mathematics
• Set theory. An introduction to independence proofs
• Independence results in computer science?
• Set theory. An introduction to large cardinals
• A course in model theory. An introduction to contemporary mathematical logic. Transl. from the French by Moses Klein
• Mortality in Matrix Semigroups
• Where is the Gödel-point hiding: Gentzen’s Consistency Proof of 1936 and His Representation of Constructive Ordinals
• Incompleteness Theorems, Large Cardinals, and Automata over Finite Words
• Some problems in automata theory which depend on the models of set theory
• The Complexity of Infinite Computations In Models of Set Theory
• Incompleteness Theorems, Large Cardinals, and Automata over Infinite Words
• Restricted one-counter machines with undecidable universe problems
• The Mathematical Import of Zermelo's Well-Ordering Theorem
• Set Theory
• Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations
• The consistency of arithmetics
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item