Algorithms for sentences over integral domains

DOI10.1016/0168-0072(90)90069-EMaRDI QIDQ920964zbMATH OpenOpenAlexFDO

Authors Elsie Sterbin Gottlieb

Publication date 1990

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(90)90069-e

zbMATH Keywords

algorithmdecidability of arithmetical \(\forall \exists \)-sentences over integral domains

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25)

Review text

Arithmetical sentences are constructed from quantifiers, equality, logical connectives, constant symbols 0 and 1, and function symbols \(+\) and \(\cdot\) (multiplication). An integral domain is an associative- commutative ring with unit and without zero divisors. The paper contains two results on decidability of arithmetical \(\forall \exists\)-sentences over integral domains. Theorem 1. There exists a polynomial time algorithm deciding whether or not an arbitrary arithmetical \(\forall \exists\)-sentence in disjunctive or conjunctive normal form is valid in every integral domain of characteristic 0. Theorem 2. The \(\forall \exists\)-theory of integral domains is decidable. (The author does not know the complexity of the corresponding algorithm).

Recommendations

• Sentences over integral domains and their computational complexities
• Polynomial time algorithms for sentences over number fields
• Computational complexity of sentences over fields
• Algebras of sentences
• From word to sentence. A computational algebraic approach to grammar
• Algorithmically efficient syntactic characterization of possibility domains
• Algorithmically efficient syntactic characterization of possibility domains
• Complexity of Sentences over Number Rings
• Decidable Sentences Over Polynomial Rings
• scientific article; zbMATH DE number 992909

Cites work

• Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time
• Computational complexity of arithmetical sentences
• Decidable fragments of field theories
• Decidable Sentences Over Polynomial Rings
• Factoring multivariate integral polynomials
• Factoring Polynomials over Algebraic Number Fields
• Factoring polynomials with rational coefficients
• Hilbert's Tenth Problem is Unsolvable
• scientific article; zbMATH DE number 3765914 (Why is no real title available?)
• scientific article; zbMATH DE number 3771690 (Why is no real title available?)
• scientific article; zbMATH DE number 3550662 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Provability and Decidability of Arithmetical Universal-Existential Sentences
• The elementary theory of finite fields

Cited in

(3)

• Sentences over integral domains and their computational complexities
• scientific article; zbMATH DE number 991688 (Why is no real title available?)
• A decision algorithm for linear sentences on a PFM

This page was built for publication: Algorithms for sentences over integral domains

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