Succinct representation, leaf languages, and projection reductions

DOI10.1006/inco.1997.2696zbMath0909.68079OpenAlexW2061161327MaRDI QIDQ1271623

Helmut Veith

Publication date: 10 November 1998

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1997.2696

zbMATH Keywords

DLOGTIMEsuccinct representation technique

Mathematics Subject Classification ID

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

Related Items (11)

Languages represented by Boolean formulas ⋮ Equality Testing of Compressed Strings ⋮ Specular Sets ⋮ Model-checking hierarchical structures ⋮ Succinct circuit representations and leaf language classes are basically the same concept ⋮ Leaf languages and string compression ⋮ Functions computable in polynomial space ⋮ The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis ⋮ Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes ⋮ Succinctness as a source of complexity in logical formalisms ⋮ On the complexity of data disjunctions.

Uses Software

• Datalog

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A characterization of the leaf language classes
• Succinct circuit representations and leaf language classes are basically the same concept
• Methods for proving completeness via logical reductions
• The complexity of combinatorial problems with succinct input representation
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Reducibility by algebraic projections
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
• Using the Hamiltonian path operator to capture NP
• A uniform approach to define complexity classes
• The dot-depth hierarchy of star-free languages is infinite
• The complexity of iterated multiplication
• Logspace and logtime leaf languages
• Complexity classes and sparse oracles
• On uniformity within \(NC^ 1\)
• Succinct representations of graphs
• Second order logic and the weak exponential hierarchies
• Languages that Capture Complexity Classes
• The computational complexity of graph problems with succinct multigraph representation
• Complete Problems Involving Boolean Labelled Structures and Projection Transactions
• PSPACE SURVIVES CONSTANT-WIDTH BOTTLENECKS
• Some Remarks on Generalized Spectra
• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• A note on succinct representations of graphs
• On balanced versus unbalanced computation trees

This page was built for publication: Succinct representation, leaf languages, and projection reductions