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

DOI10.2307/2275735MaRDI QIDQ4338318zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)