×

First-order expressibility of languages with neutral letters or: The Crane Beach conjecture. (English) Zbl 1069.03021

Summary: A language \(L\) over an alphabet \(A\) is said to have a neutral letter if there is a letter \(e\in A\) such that inserting or deleting \(e\)’s from any word in \(A^*\) does not change its membership or non-membership in \(L\).
The presence of a neutral letter affects the definability of a language in first-order logic. It was conjectured that it renders all numerical predicates apart from the order predicate useless, i.e., that if a language \(L\) with a neutral letter is not definable in first-order logic with linear order, then it is not definable in first-order logic with any set \({\mathcal N}\) of numerical predicates. Named after the location of its first, flawed, proof, this conjecture is called the Crane Beach Conjecture (CBC, for short). The CBC is closely related to uniformity conditions in circuit complexity theory and to collapse results in database theory.
We investigate the CBC in detail, showing that it fails for \({\mathcal N}= \{+,\times\}\), or, possibly stronger, for any set \({\mathcal N}\) that allows counting up to the \(m\) times iterated logarithm, for any constant \(m\). On the positive side, we prove the conjecture for the case of all monadic numerical predicates, for the addition predicate +, for the fragment \(BC(\Sigma_1)\) of first-order logic, for regular languages, and for languages over a binary alphabet. We explain the precise relation between the CBC and so-called natural-generic collapse results in database theory. Furthermore, we introduce a framework that gives better understanding of what exactly may cause a failure of the conjecture.

MSC:

03C13 Model theory of finite structures
03D05 Automata and formal grammars in connection with logical questions
68Q45 Formal languages and automata
68P15 Database theory
68Q19 Descriptive complexity and finite models
03C98 Applications of model theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ajtai, M., \( \Sigma_1^1\)-formulae on finite structures, Ann. Pure Appl. Logic, 24, 1-48 (1983) · Zbl 0519.03021
[2] Ajtai, M.; Ben-Or, M., A theorem on probabilistic constant depth computations, (STOC’8416th Annual ACM Symposium on the Theory of Computing. STOC’8416th Annual ACM Symposium on the Theory of Computing, Washington DC (1984)), 471-474
[3] Baldwin, J. T.; Benedikt, M., Embedded finite models, stability theory and the impact of order, (LICS’9813th Annual IEEE Symposium on Logic in Computer Science. LICS’9813th Annual IEEE Symposium on Logic in Computer Science, Indianapolis, IN, USA (1998)), 490-500 · Zbl 0945.03544
[4] Barrington, D. A.M.; Compton, K.; Straubing, H.; Thérien, D., Regular languages in \(NC^1\), J. Comput. System Sci., 44, 478-499 (1992) · Zbl 0757.68057
[5] Barrington, D. A.M.; Immerman, N.; Lautemann, C.; Schweikardt, N.; Thérien, D., The Crane Beach Conjecture, (LICS’0116th Annual IEEE Symposium on Logic in Computer Science. LICS’0116th Annual IEEE Symposium on Logic in Computer Science, Boston, MA, USA (2001)), 187-196
[6] Barrington, D. A.M.; Immerman, N.; Straubing, H., On uniformity within \(NC^1\), J. Comput. System Sci., 41, 274-306 (1990) · Zbl 0719.68023
[7] Belegradek, O. V.; Stolboushkin, A. P.; Taitslin, M. A., Extended order-generic queries, Ann. Pure Appl. Logic, 97, 85-125 (1999) · Zbl 0956.03035
[8] Benedikt, M.; Dong, G.; Libkin, L.; Wong, L., Relational expressive power of constraint query languages, J. ACM, 45, 1-34 (1998) · Zbl 0902.68047
[9] Benedikt, M.; Libkin, L., Expressive powerthe finite case, (Kuper, G.; Libkin, L.; Paredaens, J., Constraint Databases (2000), Springer: Springer Berlin), 55-87
[10] Denenberg, L.; Gurevich, Y.; Shelah, S., Definability by constant-depth polynomial-size circuits, Inform. Control, 70, 216-240 (1986) · Zbl 0629.94023
[11] R. Diestel, Graph Theory, Graduate Texts in Mathematics, vol. 173, 2nd ed., Springer, Berlin, 2000. Electronic version available at http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/; R. Diestel, Graph Theory, Graduate Texts in Mathematics, vol. 173, 2nd ed., Springer, Berlin, 2000. Electronic version available at http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
[12] Ebbinghaus, H.-D.; Flum, J., Finite Model Theory (1999), Springer: Springer Berlin
[13] Erdös, P.; Szekeres, G., A combinatorial problem in geometry, Compositio Math., 2, 464-470 (1935) · JFM 61.0651.04
[14] Fagin, R.; Klawe, M.; Pippenger, N.; Stockmeyer, L. J., Bounded-depth polynomial size circuits for symmetric functions, Theoret. Comput. Sci., 36, 239-250 (1985) · Zbl 0574.94024
[15] Furst, M. L.; Saxe, J. B.; Sipser, M., Parity, circuits, and the polynomial-time hierarchy, Math. Systems Theory, 17, 13-27 (1984) · Zbl 0534.94008
[16] Immerman, N., Descriptive and Computational Complexity (1999), Springer: Springer Berlin
[17] A. Krol, C. Lautemann, Modular counting in strings, Unpublished manuscript, 2002.; A. Krol, C. Lautemann, Modular counting in strings, Unpublished manuscript, 2002.
[18] G.M. Kuper, L. Libkin, J. Paredaens (Eds.), Constraint Databases, Springer, Berlin, 2000.; G.M. Kuper, L. Libkin, J. Paredaens (Eds.), Constraint Databases, Springer, Berlin, 2000. · Zbl 0935.00022
[19] Lee, T., Arithmetical definability over finite structures, Math. Logic Quart., 49, 385-392 (2003) · Zbl 1022.03015
[20] C. Lautemann, P. McKenzie, T. Schwentick, H. Vollmer, The descriptive complexity approach to LOGCFL, in: STACS’99: 16th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 1563, Springer, Berlin, 1999, pp. 444-454.; C. Lautemann, P. McKenzie, T. Schwentick, H. Vollmer, The descriptive complexity approach to LOGCFL, in: STACS’99: 16th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 1563, Springer, Berlin, 1999, pp. 444-454. · Zbl 0924.03069
[21] C. Lautemann, N. Schweikardt, An Ehrenfeucht-Fraı¨ssé approach to collapse results for first-order queries over embedded databases, in: STACS’01: 18th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2010, Springer, Berlin, 2001, pp. 455-466; C. Lautemann, N. Schweikardt, An Ehrenfeucht-Fraı¨ssé approach to collapse results for first-order queries over embedded databases, in: STACS’01: 18th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2010, Springer, Berlin, 2001, pp. 455-466 · Zbl 0976.68047
[22] L. Libkin, Embedded finite models and constraint databases. in: E. Grädel, P.G. Kolaitis, L. Libkin, M. Marx, J. Spencer, M.Y. Vardi, Y. Venema, S. Weinstein (Eds.), Finite Model Theory and Its Applications, Springer-Verlag, 2005.; L. Libkin, Embedded finite models and constraint databases. in: E. Grädel, P.G. Kolaitis, L. Libkin, M. Marx, J. Spencer, M.Y. Vardi, Y. Venema, S. Weinstein (Eds.), Finite Model Theory and Its Applications, Springer-Verlag, 2005.
[23] Lynch, J. F., Complexity classes and theories of finite models, Math. Systems Theory, 15, 127-144 (1982) · Zbl 0484.03020
[24] Lynch, J. F., On sets of relations definable by addition, J. Symbolic Logic, 47, 659-668 (1982) · Zbl 0504.03013
[25] N. Schweikardt, On the expressive power of first-order logic with built-in predicates, Ph.D. Thesis, Johannes Gutenberg-Universität Mainz, Fachbereich Mathematik und Informatik, 2001. Published at Logos-Verlag, Berlin, 2002, ISBN 3-8325-0017-0.; N. Schweikardt, On the expressive power of first-order logic with built-in predicates, Ph.D. Thesis, Johannes Gutenberg-Universität Mainz, Fachbereich Mathematik und Informatik, 2001. Published at Logos-Verlag, Berlin, 2002, ISBN 3-8325-0017-0.
[26] N. Schweikardt, An Ehrenfeucht-Fraı¨ssé game approach to collapse results in database theory, CoRR Report, arXiv:cs.LO/0212049, 20 December 2002, 70 pp, Submitted for publication.; N. Schweikardt, An Ehrenfeucht-Fraı¨ssé game approach to collapse results in database theory, CoRR Report, arXiv:cs.LO/0212049, 20 December 2002, 70 pp, Submitted for publication.
[27] N. Schweikardt, Arithmetic, first-order logic, and counting quantifiers, ACM Trans. Comput. Logic 2004, 35 p, to appear.; N. Schweikardt, Arithmetic, first-order logic, and counting quantifiers, ACM Trans. Comput. Logic 2004, 35 p, to appear. · Zbl 1407.03050
[28] N. Schweikardt, T. Schwentick, Unpublished manuscript on Monadic NP with built-in grid structures.; N. Schweikardt, T. Schwentick, Unpublished manuscript on Monadic NP with built-in grid structures.
[29] T. Schwentick, Padding and the expressive power of existential second-order logics, in: CSL’97: Annual Conference of the European Association for Computer Science Logic, Lecture Notes in Computer Science, vol. 1414, Springer, Berlin, 1997, pp. 461-477.; T. Schwentick, Padding and the expressive power of existential second-order logics, in: CSL’97: Annual Conference of the European Association for Computer Science Logic, Lecture Notes in Computer Science, vol. 1414, Springer, Berlin, 1997, pp. 461-477.
[30] Smoryński, C., Logical Number Theory I (1991), Springer: Springer Berlin · Zbl 0759.03002
[31] Straubing, H., Finite Automata, Formal Logic, and Circuit Complexity (1994), Birkhäuser: Birkhäuser Basel · Zbl 0816.68086
[32] Straubing, H., Languages defined with modular counting quantifiers, Inform. Comput., 166, 112-132 (2001) · Zbl 1007.68071
[33] M.A. Taitslin, Translation results in database theory, in: Complex systems: data processing, simulation, and optimization, Tver State University, Tver, 2002, pp. 5-23. (Russian. An English abstract was presented at the FMT’03 meeting in Bedlewo, Poland).; M.A. Taitslin, Translation results in database theory, in: Complex systems: data processing, simulation, and optimization, Tver State University, Tver, 2002, pp. 5-23. (Russian. An English abstract was presented at the FMT’03 meeting in Bedlewo, Poland).
[34] J. Van den Bussche, Applications of Alfred Tarski’s ideas in database theory, in: CSL’01: Annual Conference of the European Association for Computer Science Logic, Lecture Notes in Computer Science, vol. 2142, Springer, 2001, pp. 20-37.; J. Van den Bussche, Applications of Alfred Tarski’s ideas in database theory, in: CSL’01: Annual Conference of the European Association for Computer Science Logic, Lecture Notes in Computer Science, vol. 2142, Springer, 2001, pp. 20-37. · Zbl 0999.68055
[35] I. Wegener, N. Wurm, S.-Z. Yi, Symmetric functions in \(\mathit{AC}^0\); I. Wegener, N. Wurm, S.-Z. Yi, Symmetric functions in \(\mathit{AC}^0\) · Zbl 0769.68051
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.