Immerman, Neil Languages that capture complexity classes. (English) Zbl 0634.68034 SIAM J. Comput. 16, 760-778 (1987). Some results on interrelations between the problems expressible by logical languages and the complexity classes are proved. The set \(1^{st}O\) of all finite models of the first order languages is strictly contained in the complexity class L (deterministic logspace). Adding the operator pos TC of the positive reflexive transitive closure of the relations, the author proves the coincidence \(NL=1^{st}O+pos TC\). Moreover \(L=1^{st}O+DTC\), where DTC is the deterministic version of the transitive closure. Similar results on the descriptions of the polynomially space complexity classes in the terms of second order logical languages are ascertained, in particular \(PSPACE=2^{nd}O+TC\). Reviewer: D.Yu.Grigor’ev Cited in 3 ReviewsCited in 131 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 03D15 Complexity of computation (including implicit computational complexity) Keywords:bounded depth circuits; quantifier alternations; logical languages; transitive closure; complexity classes PDF BibTeX XML Cite \textit{N. Immerman}, SIAM J. Comput. 16, 760--778 (1987; Zbl 0634.68034) Full Text: DOI Link OpenURL