A descriptive complexity approach to the linear hierarchy.
From MaRDI portal
Publication:1401413
DOI10.1016/S0304-3975(03)00133-6zbMATH Open1044.68092MaRDI QIDQ1401413FDOQ1401413
Authors: Yassine Hachaïchi 
Publication date: 17 August 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Recommendations
- scientific article; zbMATH DE number 1342206
- scientific article; zbMATH DE number 1114020
- On the Descriptive Complexity of Linear Algebra
- scientific article; zbMATH DE number 1978903
- Logical Approaches to Computational Barriers
- ON THE DESCRIPTIONAL COMPLEXITY OF LINDENMAYER SYSTEMS
- scientific article; zbMATH DE number 1424025
- Descriptive complexity of linear equation systems and applications to propositional proof complexity
- Descriptive complexity: a logician's approach to computation.
- scientific article; zbMATH DE number 1948492
Monadic second-order logicDescriptive complexityGeneralized quantifiersLinear hierarchyRudimentary languages
Cites Work
- Title not available (Why is that?)
- The polynomial-time hierarchy
- Languages that Capture Complexity Classes
- Weak Second‐Order Arithmetic and Finite Automata
- Decision Problems of Finite Automata Design and Related Arithmetics
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Theory of Formal Systems. (AM-47)
- Complexity classes and theories of finite models
- Concatenation as a basis for arithmetic
- Title not available (Why is that?)
- A logical approach of Petri net languages
- Sorting, linear time and the satisfiability problem
- ON THE NOTION OF LINEAR TIME COMPUTABILITY
- Rudimentary Predicates and Relative Computation
- Title not available (Why is that?)
Cited In (2)
This page was built for publication: A descriptive complexity approach to the linear hierarchy.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1401413)
