Simple sentences that are hard to decide
type: Item
instance of: scholarly article
title: Simple sentences that are hard to decide
zbMATH Open document ID: 0733.03031
DOI: 10.1016/0890-5401(91)90033-X
author: Erich Grädel
published in: Information and Computation
publication date: 1991-01-01T00:00:00Z
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 03D10
zbMATH DE Number: 4212026
zbMATH Keywords: restrictions of first-order theories
zbMATH Keywords: limited number of quantifier alternations
zbMATH Keywords: domino games
zbMATH Keywords: time complexity
zbMATH Keywords: exponential time
MaRDI profile type: Publication
cites work: The undecidability of the domino problem
cites work: Q3220555
cites work: Domino-tiling games
cites work: A uniform method for proving lower bounds on the computational complexity of logical theories
cites work: The complexity of Presburger arithmetic with bounded quantifier alternation depth
cites work: Q3795666
cites work: Dominoes and the complexity of subclasses of logical theories
cites work: Domino Games and Complexity
cites work: Complexity of Boolean algebras
cites work: Presburger arithmetic with bounded quantifier alternation
cites work: Complexity of Subcases of Presburger Arithmetic
cites work: Real addition and the polynomial hierarchy
cites work: The polynomial-time hierarchy
cites work: Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
full work available at URL: 0890-5401(91)90033-x
OpenAlex ID: W2052023676
description: scientific article; zbMATH DE number 4212026