Generalized hex and logical characterizations of polynomial space
type: Item
instance of: scholarly article
title: Generalized hex and logical characterizations of polynomial space
zbMATH Open document ID: 1337.68120
DOI: 10.1016/S0020-0190(97)00116-6
author: Iain Stewart
author: A. A. Arratia-Quesada
published in: Information Processing Letters
publication date: 2016-05-26T00:00:00Z
full work available at URL: https://arxiv.org/abs/math/9612228
Mathematics Subject Classification ID: 68Q19
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 6585458
zbMATH Keywords: computational complexity
zbMATH Keywords: descriptive complexity
zbMATH Keywords: finite model theory
zbMATH Keywords: logical characterizations of polynomial space
zbMATH Keywords: completeness via logical reductions
MaRDI profile type: Publication
arXiv ID: math/9612228
cites work: Q3204028
cites work: Q3775538
cites work: Q4850061
cites work: An application of games to the completeness problem for formalized theories
cites work: Q3230355
cites work: Q4198056
cites work: Complete problems for fixed-point logics
cites work: Q4346734
cites work: Languages that Capture Complexity Classes
cites work: Q4525286
cites work: Q4395562
cites work: Comparing the Expressibility of Languages Formed Using NP-Complete Operators
cites work: Methods for proving completeness via logical reductions
cites work: Context-sensitive transitive closure operators
cites work: Completeness of path-problems via logical reductions
cites work: Logics with Zero-One Laws that Are Not Fragments of Bounded-Variable Infinitary Logic
OpenAlex ID: W1976089946
Recommended article: Logical characterization of recognizable sets of polynomials over a finite field
Recommended article: Generalized hexagons and polar spaces
Recommended article: The polyadic generalization of the Boolean axiomatization of fields of sets
Recommended article: Q4722073
Recommended article: Q3115596
Recommended article: Q5202958
Recommended article: A polynomial characterization of Hilbert spaces
Recommended article: Q4723705
Recommended article: Q3496494
Recommended article: On the superstructure of the class of polynomials in multivalued logics
description: scientific article; zbMATH DE number 6585458