A characterization of the leaf language classes

DOI10.1016/S0020-0190(97)00111-7MaRDI QIDQ287160zbMATH OpenFDO

Authors Bernd Borchert, Riccardo Silvestri

Publication date 26 May 2016

Published in Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexitytheory of computation

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Machines, Computations, and Universality
• Logspace and logtime leaf languages
• Mathematical Foundations of Computer Science 2005
• Generic separations and leaf languages
• Very Sparse Leaf Languages

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3814972 (Why is no real title available?)
• scientific article; zbMATH DE number 3896918 (Why is no real title available?)
• scientific article; zbMATH DE number 3921977 (Why is no real title available?)
• scientific article; zbMATH DE number 4037840 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 761756 (Why is no real title available?)
• scientific article; zbMATH DE number 3290336 (Why is no real title available?)
• A uniform approach to define complexity classes
• Complexity classes and sparse oracles
• Complexity classes without machines: on complete languages for UP
• Logspace and logtime leaf languages
• On balanced versus unbalanced computation trees
• On the Structure of Polynomial Time Reducibility
• On the relative complexity of hard problems for complexity classes without complete problems
• On the theory of the PTIME degrees of the recursive sets
• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• Sublattices of the polynomial time degrees

Cited in

(11)

• Generic separations and leaf languages
• Succinctness as a source of complexity in logical formalisms
• scientific article; zbMATH DE number 1418356 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2005
• Machines that can output empty words
• Machines, Computations, and Universality
• Succinct representation, leaf languages, and projection reductions
• Dot operators
• Very Sparse Leaf Languages
• THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS
• Lindström quantifiers and leaf language definability

This page was built for publication: A characterization of the leaf language classes

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