First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
type: Item
instance of: scholarly article
title: First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
zbMATH Open document ID: 1069.03021
author: David A. Mix Barrington
author: Clemens Lautemann
author: Nicole Schweikardt
author: Denis Thérien
author: Neil Immerman
published in: Journal of Computer and System Sciences
publication date: 2005-05-12T00:00:00Z
Mathematics Subject Classification ID: 03C13
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68P15
Mathematics Subject Classification ID: 68Q19
Mathematics Subject Classification ID: 03C98
zbMATH DE Number: 2167381
zbMATH Keywords: formal languages
zbMATH Keywords: relative expressive power
zbMATH Keywords: circuit uniformity
zbMATH Keywords: neutral letter
zbMATH Keywords: definability of a language in first-order logic
zbMATH Keywords: numerical predicates
zbMATH Keywords: order predicate
zbMATH Keywords: circuit complexity
zbMATH Keywords: natural-generic collapse
zbMATH Keywords: database
MaRDI profile type: Publication
full work available at URL: j.jcss.2004.07.004
OpenAlex ID: W2096648167
Wikidata QID: Q123140624
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: Q4936135
cites work: Regular languages in \(NC\)
cites work: On uniformity within \(NC^ 1\)
cites work: Extended order-generic queries
cites work: Relational expressive power of constraint query languages
cites work: Q4508937
cites work: Definability by constant-depth polynomial-size circuits
cites work: Q4947393
cites work: Q4255575
cites work: Bounded-depth, polynomial-size circuits for symmetric functions
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Q4227581
cites work: Q4935250
cites work: Arithmetical definability over finite structures
cites work: Q4251062
cites work: Q2762524
cites work: Complexity classes and theories of finite models
cites work: On sets of relations definable by addition
cites work: Arithmetic, first-order logic, and counting quantifiers
cites work: Q4218949
cites work: Logical number theory I. An introduction
cites work: Q4302435
cites work: Languages defined with modular counting quantifiers
cites work: Q4783298
cites work: Q4036705
DOI: 10.1016/J.JCSS.2004.07.004
description: scientific article; zbMATH DE number 2167381