Computational model theory: An overview Export

@misc{citeulike:960460, abstract = {The computational complexity of a problem is the amount of resources, such as time or space, required by a machine that solves the problem. The descriptive complexity of problems is the complexity of describing problems in some logical formalism over finite structures. One of the exciting developments in complexity theory is the discovery of a very intimate connection between computational and descriptive complexity. It is this connection between complexity theory and finite-model theory that...}, author = {Vardi, M.}, citeulike-article-id = {960460}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.8613}, keywords = {constructive-logics, constructive-model-theory, lattice-theory, quantales, recursive-model-theory, topos-theory}, posted-at = {2008-04-01 11:38:21}, priority = {2}, title = {Computational model theory: An overview}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.8613}, year = {1998} }

TY - GEN ID - citeulike:960460 L3 - citeulike-article-id:960460 N2 - The computational complexity of a problem is the amount of resources, such as time or space, required by a machine that solves the problem. The descriptive complexity of problems is the complexity of describing problems in some logical formalism over finite structures. One of the exciting developments in complexity theory is the discovery of a very intimate connection between computational and descriptive complexity. It is this connection between complexity theory and finite-model theory that... TI - Computational model theory: An overview KW - constructive-logics KW - constructive-model-theory KW - lattice-theory KW - quantales KW - recursive-model-theory KW - topos-theory AU - Vardi, M PY - 1998/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.8613 ER -