First-order expressibility of languages with neutral letters or: The Crane Beach conjecture

DOI10.1016/J.JCSS.2004.07.004MaRDI QIDQ1776372zbMATH OpenOpenAlexWikidataFDO

Authors David A. Mix Barrington, Clemens Lautemann, Nicole Schweikardt, Denis Thérien, Neil Immerman

Publication date 12 May 2005

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2004.07.004

zbMATH Keywords

databaseformal languagescircuit complexitycircuit uniformitydefinability of a language in first-order logicnatural-generic collapseneutral letternumerical predicatesorder predicaterelative expressive power

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Model theory of finite structures (03C13) Automata and formal grammars in connection with logical questions (03D05) Database theory (68P15) Descriptive complexity and finite models (68Q19) Applications of model theory (03C98)

Recommendations

• An Algebraic Point of View on the Crane Beach Property
• Non-definability of Languages by Generalized First-order Formulas over (N,+)
• scientific article; zbMATH DE number 7297896
• Definability of Languages by Generalized First-Order Formulas over $(\mathbb{N},+)$
• Circuit complexity and the expressive power of generalized first-order formulas

Cites work

• scientific article; zbMATH DE number 1688383 (Why is no real title available?)
• scientific article; zbMATH DE number 176874 (Why is no real title available?)
• scientific article; zbMATH DE number 1223637 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1304331 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 1515856 (Why is no real title available?)
• scientific article; zbMATH DE number 1841810 (Why is no real title available?)
• scientific article; zbMATH DE number 1395614 (Why is no real title available?)
• scientific article; zbMATH DE number 1392296 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Arithmetic, first-order logic, and counting quantifiers
• Arithmetical definability over finite structures
• Bounded-depth, polynomial-size circuits for symmetric functions
• Complexity classes and theories of finite models
• Definability by constant-depth polynomial-size circuits
• Extended order-generic queries
• Languages defined with modular counting quantifiers
• Logical number theory I. An introduction
• On sets of relations definable by addition
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• Regular languages in \(NC\)
• Relational expressive power of constraint query languages
• \(\Sigma_ 1^ 1\)-formulae on finite structures

Cited in

(6)

• An Algebraic Point of View on the Crane Beach Property
• Extensional Uniformity for Boolean Circuits
• The regular languages of wire linear \(\mathrm{AC}^0\)
• The regular languages of first-order logic with one alternation
• An Ehrenfeucht-Fraïssé game approach to collapse results in database theory
• A characterization of definability of second-order generalized quantifiers with applications to non-definability

This page was built for publication: First-order expressibility of languages with neutral letters or: The Crane Beach conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1776372)