A descriptive complexity approach to the linear hierarchy.

DOI10.1016/S0304-3975(03)00133-6zbMath1044.68092MaRDI QIDQ1401413

Yassine Hachaïchi

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Monadic second-order logicDescriptive complexityGeneralized quantifiersLinear hierarchyRudimentary languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (1)

Arithmetical definability and computational complexity

Cites Work

• A logical approach of Petri net languages
• The polynomial-time hierarchy
• Sorting, linear time and the satisfiability problem
• Theory of Formal Systems. (AM-47)
• Weak Second‐Order Arithmetic and Finite Automata
• ON THE NOTION OF LINEAR TIME COMPUTABILITY
• Languages that Capture Complexity Classes
• Decision Problems of Finite Automata Design and Related Arithmetics
• Complexity classes and theories of finite models
• Rudimentary Predicates and Relative Computation
• Concatenation as a basis for arithmetic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A descriptive complexity approach to the linear hierarchy.