Succinct representation, leaf languages, and projection reductions
From MaRDI portal
Publication:1271623
DOI10.1006/inco.1997.2696zbMath0909.68079OpenAlexW2061161327MaRDI QIDQ1271623
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
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
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
