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

circuit complexitycircuit uniformitydatabasedefinability of a language in first-order logicformal languagesnatural-generic collapseneutral letternumerical predicatesorder predicaterelative expressive power

Mathematics Subject Classification ID

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

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

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• An Ehrenfeucht-Fraïssé approach to collapse results for first-order queries over embedded databases
• Applications of Alfred Tarski's ideas in database theory
• 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
• Constraint databases
• Definability by constant-depth polynomial-size circuits
• Descriptive complexity
• Expressive power: The finit case
• Extended order-generic queries
• Finite model theory.
• Graph theory.
• scientific article; zbMATH DE number 176874 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 1392296 (Why is no real title available?)
• Languages defined with modular counting quantifiers
• Logical number theory I. An introduction
• On sets of relations definable by addition
• On uniformity within \(NC^ 1\)
• Padding and the expressive power of existential second-order logics
• Parity, circuits, and the polynomial-time hierarchy
• Regular languages in \(NC\)
• Relational expressive power of constraint query languages
• The descriptive complexity approach to LOGCFL

Cited in

(8)

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

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)