Large Finite Structures with Few Lk-Types

Author： Grohe M.  

Publisher： Academic Press

ISSN： 0890-5401

Source： Information and Computation, Vol.179, Iss.2, 2002-12, pp. : 250-278

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

For any k≥3, we prove the following results on theories in the k-variable fragment Lk of first-order logic:(1) The so-called Lk-invariant is not recursively invertible.(2) There is no recursive bound on the size of the minimal model of a complete Lk-theory in terms of its k-size, that is, the number of its Lk-types.(3) Assume that NP⊈P/poly. Then there is no P-computable canonization function for Lk-equivalence.Our results answer questions of Dawar [3, 4] and Dawar, Lindell, and Weinstein [5]. © 2002 Elsevier Science (USA).

Related content

A Finite Difference Scheme for the K(2, 2) Compacton Equation

By deFrutos J.   López-Marcos M.A.   Sanz-Serna J.M.  

Journal of Computational Physics, Vol. 120, Iss. 2, 1995-09 ,pp. : 248-252 (5)

Academic Press

Access to resources Recommend Favorite

Quasirecognition by prime graph of finite simple groups L n (2) and U n (2)

By Khosravi Behrooz   Moradi Hossein  

Acta Mathematica Hungarica, Vol. 132, Iss. 1-2, 2011-07 ,pp. : 140-153 (14)

Springer Publishing Company

Access to resources Recommend Favorite

On Lie k-Algebras

By Hanlon P.   Wachs M.  

Advances in Mathematics, Vol. 113, Iss. 2, 1995-07 ,pp. : 206-236 (31)

Academic Press

Access to resources Recommend Favorite

A note on 2 -nilpotence of finite groups

By SHI JIANGTAO  

Proceedings Mathematical Sciences, Vol. 123, Iss. 2, 2013-05 ,pp. : 235-238 (4)

Springer Publishing Company

Access to resources Recommend Favorite

The k-Steiner Ratio in the Rectilinear Plane

By Borchers A.   Du D-Z.   Gao B.   Wan P.  

Journal of Algorithms, Vol. 29, Iss. 1, 1998-10 ,pp. : 1-17 (17)

Academic Press

Access to resources Recommend Favorite