Portal de Periódicos da CAPES

The Computational Complexity of Logical Theories

1979; Springer Nature; Linguagem: Inglês

10.1007/bfb0062837

1617-9692

Jeanne Ferrante, Charles Rackoff,

Advanced Algebra and Logic

and background.- Ehrenfeucht games and decision procedures.- Integer addition - An example of an Ehrenfeucht game decision procedure.- Some additional upper bounds.- Direct products of theories.- Lower bound preliminaries.- A technique for writing short formulas defining complicated properties.- A lower bound on the theories of pairing functions.- Some additional lower bounds.