Limiting characterizations of low level space complexity classes

DOI10.1051/ITA/1993270301751MaRDI QIDQ3142271zbMATH OpenOpenAlexFDO

Authors Michele Angelaccio, Marco Protasi

Publication date 15 November 1993

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92447

zbMATH Keywords

complexity theoryspace complexity classeslimiting recursion

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• LIMITING POLYNOMIAL APPROXIMATION OF COMPLEXITY CLASSES
• Neat function algebraic characterizations of LOGSPACE and LINSPACE
• LOGSPACE and PTIME characterized by programming languages
• A survey of space complexity
• Characterizing small depth and small space classes by operators of higher types

Cites work

• scientific article; zbMATH DE number 3936518 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• LIMITING POLYNOMIAL APPROXIMATION OF COMPLEXITY CLASSES
• Limiting recursion
• The polynomial-time hierarchy
• Trial and error predicates and the solution to a problem of Mostowski

This page was built for publication: Limiting characterizations of low level space complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3142271)