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

DOI10.1016/J.JCSS.2004.07.004zbMATH Open1069.03021OpenAlexW2096648167WikidataQ123140624 ScholiaQ123140624MaRDI QIDQ1776372FDOQ1776372

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

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

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)

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• On uniformity within \(NC^ 1\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Parity, circuits, and the polynomial-time hierarchy
• Title not available (Why is that?)
• Regular languages in \(NC\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity classes and theories of finite models
• Extended order-generic queries
• Arithmetical definability over finite structures
• Title not available (Why is that?)
• Arithmetic, first-order logic, and counting quantifiers
• Title not available (Why is that?)
• Definability by constant-depth polynomial-size circuits
• Relational expressive power of constraint query languages
• Bounded-depth, polynomial-size circuits for symmetric functions
• Title not available (Why is that?)
• On sets of relations definable by addition
• Title not available (Why is that?)
• Logical number theory I. An introduction
• Languages defined with modular counting quantifiers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (6)

• 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
• An Algebraic Point of View on the Crane Beach Property

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)