Upper and lower bounds for first order expressibility
type: Item
instance of: scholarly article
title: Upper and lower bounds for first order expressibility
zbMATH Open document ID: 0503.68032
DOI: 10.1016/0022-0000(82)90011-3
published in: Journal of Computer and System Sciences
publication date: 1982-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 3793408
zbMATH Keywords: time/space complexity
zbMATH Keywords: first order expressibility as a measure of complexity
zbMATH Keywords: Turing machines
zbMATH Keywords: alternating pebbling game
zbMATH Keywords: combinatorial properties in the language without ordering
MaRDI profile type: Publication
full work available at URL: 0022-0000(82)90011-3
OpenAlex ID: W1984581643
cites work: Q4091421
cites work: Properties of almost all graphs and complexes
cites work: An application of games to the completeness problem for formalized theories
cites work: Q4052071
cites work: Q4058132
cites work: Probabilities on finite models
cites work: Q4082296
cites work: Number of quantifiers is better than number of tape cells
cites work: Almost sure theories
cites work: Maze recognizing automata and nondeterministic tape complexity
cites work: On the Tape Complexity of Deterministic Context-Free Languages
author: Neil Immerman
description: scientific article; zbMATH DE number 3793408