Critical theories of some classes of graphs and unary algebras (Q2639043)

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.