Undecidability of the first-order arithmetic A[P(x),2x,x+1]

DOI10.1016/0022-0000(79)90033-3MaRDI QIDQ599047zbMATH OpenOpenAlexFDO

Authors Sumit K. Garg

Publication date 1979

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(79)90033-3

zbMATH Keywords

first order arithmeticfirst order theorymonadic second order theoryreachability problemsatisfiability problemtwo dimensional finite automataundecidability

Mathematics Subject Classification ID

Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) Automata and formal grammars in connection with logical questions (03D05) Decidability (number-theoretic aspects) (11U05)

Cites work

• Decidability and essential undecidability
• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
• On causal ^2-systems
• Restricted Set-Theoretical Definitions in Arithmetic
• Weak Second‐Order Arithmetic and Finite Automata

This page was built for publication: Undecidability of the first-order arithmetic \(A[P(x),2x,x+1]\)

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