The theory of integer multiplication with order restricted to primes is decidable

DOI10.2307/2275735zbMATH Open0881.03008OpenAlexW2034177508MaRDI QIDQ4338318FDOQ4338318

Authors: Françoise Maurin 

Publication date: 28 May 1997

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

Full work available at URL: https://doi.org/10.2307/2275735

Recommendations

• Decidability and undecidability of theories with a predicate for the primes
• Decidability and classification of the theory of integers with primes
• scientific article; zbMATH DE number 221693
• On the additive theory of prime numbers

zbMATH Keywords

complexityinteger multiplicationquantifier eliminationtower of exponentials

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Quantifier elimination, model completeness, and related topics (03C10)

Cites Work

• A Decision Procedure for the First Order Theory of Real Addition with Order
• Weak Second‐Order Arithmetic and Finite Automata
• Definability and decision problems in arithmetic
• The computational complexity of logical theories
• A uniform method for proving lower bounds on the computational complexity of logical theories

Cited In (8)

• Decidability and definability results related to the elementary theory of ordinal multiplication
• Multitree automata that count
• Decidability and undecidability of theories with a predicate for the primes
• Complexity of logical theories involving coprimality
• Some new results in monadic second-order arithmetic
• Undecidable extensions of Skolem arithmetic
• Decidability and classification of the theory of integers with primes
• Exact complexity bounds for ordinal addition

This page was built for publication: The theory of integer multiplication with order restricted to primes is decidable

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