Existential Diophantine definability of string length

DOI10.1016/J.TCS.2018.11.032MaRDI QIDQ2419123zbMATH OpenOpenAlexFDO

Authors Bruce Litow

Publication date 29 May 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2018.11.032

zbMATH Keywords

doubly exponential sizeexistential Diophantineinteger exponentiation

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Decidability (number-theoretic aspects) (11U05)

Recommendations

• THE EXPONENTIAL DIOPHANTINE PROBLEM FOR
• scientific article; zbMATH DE number 1261118
• A Note on Diophantine Representations
• Reduction of unknowns in diophantine representations
• Classification of Quantifier Prefixes Over Exponential Diophantine Equations

Cites work

• Decidability and local-global principles
• Defining Z in Q
• Hilbert's Tenth Problem is Unsolvable
• Hilbert's Tenth Problem over number fields, a survey
• Hilbert's tenth problem. Diophantine classes and extensions to global fields
• Hilbert's Tenth Problem: What was done and what is to be done
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 42574 (Why is no real title available?)
• scientific article; zbMATH DE number 3539209 (Why is no real title available?)
• Undecidability of existential theories of rings and fields: A survey

This page was built for publication: Existential Diophantine definability of string length

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