The Descriptive Complexity of the Deterministic Exponential Time Hierarchy

DOI10.1016/j.entcs.2011.03.006zbMath1347.68176OpenAlexW2057322444WikidataQ113318276 ScholiaQ113318276MaRDI QIDQ5179012

Cibele Matos Freire, Ana Teresa Martins

Publication date: 18 March 2015

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

Full work available at URL: https://doi.org/10.1016/j.entcs.2011.03.006

zbMATH Keywords

descriptive complexityhigher-order logicsfixed-point operatordeterministic exponential time hierarchy

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptive characterizations of computational complexity
• On the expressive power of database queries with intermediate types
• The polynomial-time hierarchy
• Computing queries with higher-order logics
• A lattice-theoretical fixpoint theorem and its applications
• Expressibility of Higher Order Logics

This page was built for publication: The Descriptive Complexity of the Deterministic Exponential Time Hierarchy