Closure and nonclosure properties of the classes of compressible and rankable sets
From MaRDI portal
Publication:2037201
DOI10.1016/j.jcss.2021.02.004OpenAlexW3136383125MaRDI QIDQ2037201
Jackson Abascal, Shir Maimon, Daniel Rubery, Hemaspaandra, Lane A.
Publication date: 30 June 2021
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2021.02.004
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Closure properties and descriptional complexity of deterministic regular expressions
- Closure properties of pattern languages
- P-selectivity: Intersections and indices
- Avoiding simplicity is complex
- On the complexity of ranking
- Complexity and structure
- The method of forced enumeration for nondeterministic automata
- The complexity of computing the number of strings of given length in context-free languages
- Polynomial-time compression
- A very hard log-space counting class
- Boolean operations, joins, and the extended low hierarchy
- Scalability and the isomorphism problem
- Easy sets and hard certificate schemes
- Inverting onto functions.
- Ranking and unranking permutations in linear time
- Recursion-theoretic ranking and compression
- Copyless cost-register automata: structure, expressiveness, and closure properties
- Tally NP sets and easy census functions.
- Ranking and unranking fixed-density necklaces and Lyndon words
- Closure and nonclosure properties of the compressible and rankable sets
- On decidability and closure properties of language classes with respect to bio-operations
- Lexicographic ranking and unranking of derangements in cycle notation
- A generic approach for the unranking of labeled combinatorial classes
- Resource-Bounded Kolmogorov Complexity Revisited
- The complexity of ranking simple languages
- Retraceable Sets
- Ranking/Unranking of Lambda Terms with Compressed de Bruijn Indices
- Sparse Sets, Lowness and Highness
- Complexity Measures for Public-Key Cryptosystems
- Nondeterministic Space is Closed under Complementation
- Compression and Ranking
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Closure properties of synchronized relations
- Further closure properties of input-driven pushdown automata
- Theory of semi-feasible algorithms
