A descriptive complexity approach to the linear hierarchy.
type: Item
instance of: scholarly article
title: A descriptive complexity approach to the linear hierarchy.
zbMATH Open document ID: 1044.68092
DOI: 10.1016/S0304-3975(03)00133-6
author: Yassine Hachaïchi
published in: Theoretical Computer Science
publication date: 2003-08-17T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1965407
zbMATH Keywords: Rudimentary languages
zbMATH Keywords: Linear hierarchy
zbMATH Keywords: Descriptive complexity
zbMATH Keywords: Monadic second-order logic
zbMATH Keywords: Generalized quantifiers
MaRDI profile type: Publication
cites work: Weak Second‐Order Arithmetic and Finite Automata
cites work: Q4255575
cites work: Decision Problems of Finite Automata Design and Related Arithmetics
cites work: ON THE NOTION OF LINEAR TIME COMPUTABILITY
cites work: Sorting, linear time and the satisfiability problem
cites work: Q4474839
cites work: Q3826533
cites work: Languages that Capture Complexity Classes
cites work: Q4227581
cites work: Q4251045
cites work: Complexity classes and theories of finite models
cites work: A logical approach of Petri net languages
cites work: Concatenation as a basis for arithmetic
cites work: Theory of Formal Systems. (AM-47)
cites work: The polynomial-time hierarchy
cites work: Q5723184
cites work: Rudimentary Predicates and Relative Computation
Recommended article: Q4263790
Recommended article: Q4375789
Recommended article: On the Descriptive Complexity of Linear Algebra
Recommended article: Q4425337
Recommended article: Logical Approaches to Computational Barriers
Recommended article: ON THE DESCRIPTIONAL COMPLEXITY OF LINDENMAYER SYSTEMS
Recommended article: Q4945215
Recommended article: Q5144627
Recommended article: Descriptive complexity: a logician's approach to computation.
Recommended article: Q4412105
description: scientific article; zbMATH DE number 1965407