The descriptive complexity of decision problems through logics with relational fixed-point and capturing results
type: Item
instance of: scholarly article
title: The descriptive complexity of decision problems through logics with relational fixed-point and capturing results
zbMATH Open document ID: 1401.68105
author: Márcia Farias
author: Ana Teresa Martins
author: Francicleber Ferreira
publication date: 2018-04-23T00:00:00Z
Mathematics Subject Classification ID: 68Q19
Mathematics Subject Classification ID: 03B70
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 6862973
zbMATH Keywords: descriptive complexity
zbMATH Keywords: fixed-point logic
zbMATH Keywords: relational fixed-point logic
zbMATH Keywords: expressiveness
MaRDI profile type: Publication
full work available at URL: j.entcs.2017.04.008
OpenAlex ID: W2666358762
cites work: Q4864249
cites work: Datalog extensions for database queries and updates
cites work: Fixpoint logics, relational machines, and computational complexity
cites work: Weak Second‐Order Arithmetic and Finite Automata
cites work: Model theory.
cites work: A relational model of data for large shared data banks
cites work: Q4255575
cites work: Q4298571
cites work: Q4058132
cites work: Finite model theory and its applications.
cites work: Fixed-point extensions of first-order logic
cites work: Q4003410
cites work: Q4227581
cites work: Q4298260
cites work: The polynomial-time hierarchy
Wikidata QID: Q113317595
DOI: 10.1016/J.ENTCS.2017.04.008
Recommended article: Q4346734
Recommended article: Fixpoint logics, relational machines, and computational complexity
Recommended article: Decidability of Circumscribed Description Logics Revisited
Recommended article: Q4503911
Recommended article: Q2753672
Recommended article: The complexity of finite model reasoning in description logics
Recommended article: The complexity of decision procedures in relevance logic II
Recommended article: Q3179028
Recommended article: A Step Up in Expressiveness of Decidable Fixpoint Logics
description: scientific article; zbMATH DE number 6862973