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

DOI10.1016/0020-0190(96)00096-8zbMath0875.68429OpenAlexW2016550752MaRDI QIDQ671606

Antoni Lozano, Bernd Borchert

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)

Related Items

UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS ⋮ Languages represented by Boolean formulas ⋮ Equality Testing of Compressed Strings ⋮ Model-checking hierarchical structures ⋮ Leaf languages and string compression ⋮ Succinct representation, leaf languages, and projection reductions ⋮ LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY ⋮ Succinctness as a source of complexity in logical formalisms ⋮ On the complexity of data disjunctions.

Cites Work

• A uniform approach to define complexity classes
• Succinct representation, leaf languages, and projection reductions
• Logspace and logtime leaf languages
• Complexity classes and sparse oracles
• Succinct representations of graphs
• Computational Work and Time on Finite Machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item