This article is cited in 1 paper

Recognition complexity of theories and their computational expressivity

I. V. Latkin

East Kazakhstan State Technical University named after D. Serikbayev, Ust-Kamenogorsk, Kazakhstan

Abstract: Computational complexity of a theory for a class $\mathfrak B$ of Boolean algebras is evaluated. We introduce a concept of computational expressivity for a theory, which is close in meaning to its computational complexity, but, as distinct from the latter, also fits well with undecidable theories.

Keywords: Boolean algebra, theory, computational expressivity of theories.

UDC: 510.52+510.58

Received: 03.05.2011
Revised: 11.03.2012

 English version: Algebra and Logic, 2012, 51:2, 144–159

Bibliographic databases:

• 
• 
• 
•