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

descriptionPublicationkeyboard_double_arrow_right Article 01 Mar 1997 English Publisher:Cambridge University Press (CUP)Journal:Journal of Symbolic Logic, volume 62, pages 123-130 (issn: 0022-4812, eissn: 1943-5886,

Copyright policy )

Authors: Françoise Maurin;

doi: 10.2307/2275735

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

- Summary
- Subjects
- Metrics

Abstract

AbstractWe show here that the first order theory of the positive integers equipped with multiplication remains decidable when one adds to the language the usual order restricted to the prime numbers. We see moreover that the complexity of the latter theory is a tower of exponentials, of height O(n).

Related Organizations

University of Caen Lower Normandy
France
Université de Caen Normandie
France

Keywords

Decidability of theories and sets of sentences, quantifier elimination, Quantifier elimination, model completeness, and related topics, tower of exponentials, integer multiplication, complexity

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	5
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average