Succinct circuit representations and leaf language classes are basically the same concept

DOI10.1016/0020-0190(96)00096-8MaRDI QIDQ671606zbMATH OpenOpenAlexFDO

Authors Bernd Borchert, Antoni Lozano

Publication date 27 February 1997

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

Full work available at URL https://doi.org/10.1016/0020-0190(96)00096-8

zbMATH Keywords

Computational complexityLeaf language classesPolynomial-time many-one completenessSuccinct representations

Mathematics Subject Classification ID

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

Recommendations

• Succinct representation, leaf languages, and projection reductions
• Machines, Computations, and Universality
• A characterization of the leaf language classes
• Mathematical Foundations of Computer Science 2005

Cites work

• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 761756 (Why is no real title available?)
• A uniform approach to define complexity classes
• Complexity classes and sparse oracles
• Computational Work and Time on Finite Machines
• Logspace and logtime leaf languages
• Succinct representation, leaf languages, and projection reductions
• Succinct representations of graphs

Cited in

(9)

• Leaf languages and string compression
• Succinctness as a source of complexity in logical formalisms
• Model-checking hierarchical structures
• On the complexity of data disjunctions.
• Equality Testing of Compressed Strings
• Succinct representation, leaf languages, and projection reductions
• UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS
• Languages represented by Boolean formulas
• Lindström quantifiers and leaf language definability

This page was built for publication: Succinct circuit representations and leaf language classes are basically the same concept

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