Critical theories of some classes of graphs and unary algebras

DOI10.1007/BF01982020MaRDI QIDQ2639043zbMATH OpenFDO

Authors S. V. Sizyj

Publication date 1989

Published in Algebra and Logic (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/187482

zbMATH Keywords

critical theoriesgraphsscheme-alternative hierarchyunary algebras

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Graph theory (05C99) Unary algebras (08A60)

Review text

This paper is based on the work of \textit{Yu. L. Ershov} [Algebra Logika 7, No.3, 38-47 (1968; Zbl 0201.008)] who gave an example of a totally ordered set whose elementary theory is undecidable, yet all the theories with a bounded number of quantifier changes are decidable. \textit{Yu. M. Vazhenin} [Sib. Mat. Zh. 29, No.1, 23-31 (1988; Zbl 0638.03013)] proposed a scheme- alternative (SA) hierarchy of first-order languages and stated the problem of finding, within SA, all decidable bounded theories for a given class of algebraic systems. The present author gives a description of SA- critical theories (i.e. minimal in SA undecidable bounded theories) for the class of all unary algebras and for certain important classes of graphs.

Recommendations

• scientific article; zbMATH DE number 4055566
• scientific article; zbMATH DE number 4039851
• Hereditary undecidability of some theories of finite structures
• Critical theories of certain nonassociative rings
• Undecidable fragments of elementary theories

Cites work

• Existential interpretation. II
• scientific article; zbMATH DE number 4012584 (Why is no real title available?)
• scientific article; zbMATH DE number 4039851 (Why is no real title available?)
• scientific article; zbMATH DE number 4055566 (Why is no real title available?)
• scientific article; zbMATH DE number 3460261 (Why is no real title available?)
• scientific article; zbMATH DE number 3318637 (Why is no real title available?)

Cited in

(3)

• Critical theories of varieties of nilpotent rings
• scientific article; zbMATH DE number 4055566 (Why is no real title available?)
• Characteristics of structurally finite classes of order-preserving three-valued logic maps

This page was built for publication: Critical theories of some classes of graphs and unary algebras

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