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

DOI10.1016/j.jcss.2004.07.004zbMath1069.03021OpenAlexW2096648167WikidataQ123140624 ScholiaQ123140624MaRDI QIDQ1776372

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

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

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

Mathematics Subject Classification ID

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

Related Items (4)

An Ehrenfeucht-Fraïssé game approach to collapse results in database theory ⋮ The regular languages of wire linear \(\mathrm{AC}^0\) ⋮ Extensional Uniformity for Boolean Circuits ⋮ A characterization of definability of second-order generalized quantifiers with applications to non-definability

Cites Work

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

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