Space-bounded reducibility among combinatorial problems
From MaRDI portal
Publication:1221749
DOI10.1016/S0022-0000(75)80050-XzbMath0317.02039OpenAlexW1989887898MaRDI QIDQ1221749
Publication date: 1975
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(75)80050-x
Analysis of algorithms and problem complexity (68Q25) Computability and recursion theory (03D99) Turing machines and related notions (03D10)
Related Items (only showing first 100 items - show all)
Equivalence classes and conditional hardness in massively parallel computations ⋮ Gradually intractable problems and nondeterministic log-space lower bounds ⋮ Deciding definability by deterministic regular expressions ⋮ Hierarchical information and the synthesis of distributed strategies ⋮ Spanning the spectrum from safety to liveness ⋮ An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines ⋮ Completeness for nondeterministic complexity classes ⋮ Infinity problems and countability problems for \(\omega \)-automata ⋮ On path equivalence of nondeterministic finite automata ⋮ Simultaneous (poly-time, log-space) lower bounds ⋮ Counting quantifiers, successor relations, and logarithmic space ⋮ Unnamed Item ⋮ The complexity of pure literal elimination ⋮ Alternating multihead finite automata ⋮ Characterization of idempotent transformation monoids ⋮ Problems concerning fairness and temporal logic for conflict-free Petri nets ⋮ Balancing bounded treewidth circuits ⋮ Inherent Vacuity in Lattice Automata ⋮ Entanglement and the complexity of directed graphs ⋮ On linear languages recognized by deterministic biautomata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The complexity of searching implicit graphs ⋮ The isomorphism conjecture for constant depth reductions ⋮ Boundary sets of regular and context-free languages ⋮ On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\) ⋮ A recognition and parsing algorithm for arbitrary conjunctive grammars. ⋮ Tree-size bounded alternation ⋮ The complexity of decision problems for finite-turn multicounter machines ⋮ Classifying the computational complexity of problems ⋮ On the computational complexity of problems related to distinguishability sets ⋮ On the descriptional complexity of stateless deterministic ordered restarting automata ⋮ Endmarkers can make a difference ⋮ Unnamed Item ⋮ Parallel models of computation: An introductory survey ⋮ Number of quantifiers is better than number of tape cells ⋮ Symmetric space-bounded computation ⋮ A note on algebras of languages ⋮ On eliminating nondeterminism from Turing machines which use less than logarithm worktape space ⋮ On the computational complexity of satisfiability in propositional logics of programs ⋮ Unifiability is complete for co-N Log Space ⋮ Distributed XML design ⋮ A note on the space complexity of some decision problems for finite automata ⋮ Iterated stack automata and complexity classes ⋮ Oracle branching programs and Logspace versus \(P^*\) ⋮ Deciding determinism of regular languages ⋮ Constrained synchronization and commutativity ⋮ Fifty years of the spectrum problem: survey and new results ⋮ Concurrent reachability games ⋮ Knapsack problems for NL ⋮ Multihead two-way probabilistic finite automata ⋮ On the equivalence of recursive and nonrecursive Datalog programs ⋮ The complexity of circuit value and network stability ⋮ The complexity of searching succinctly represented graphs ⋮ New problems complete for nondeterministic log space ⋮ Relativization of questions about log space computability ⋮ Methods for proving completeness via logical reductions ⋮ Path-disruption games: bribery and a probabilistic model ⋮ Infinite games with finite knowledge gaps ⋮ A very hard log-space counting class ⋮ Rewriting of regular expressions and regular path queries ⋮ Minimizing finite automata is computationally hard ⋮ Two-way unary automata versus logarithmic space ⋮ Decision problems for convex languages ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Complexity of universality and related problems for partially ordered NFAs ⋮ Polynomial and abstract subrecursive classes ⋮ The role of rudimentary relations in complexity theory ⋮ The Simple Reachability Problem in Switch Graphs ⋮ Complete problems for deterministic polynomial time ⋮ The polynomial-time hierarchy ⋮ Complexity of some problems in Petri nets ⋮ Corrigendum: Space-bounded reducibility among combinatorial problems ⋮ Complete sets and the polynomial-time hierarchy ⋮ On inverse deterministic pushdown transductions ⋮ On the complexity of some two-person perfect-information games ⋮ On languages specified by relative acceptance ⋮ On log-tape isomorphisms of complete sets ⋮ Prime languages ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ The complexity of properties of transformation semigroups ⋮ The complexity of the membership problem for some extensions of context-free languagest† ⋮ On the complexity of topological sorting ⋮ Investigations Concerning the Structure of Complete Sets ⋮ Sorting, linear time and the satisfiability problem ⋮ Prediction-preserving reducibility ⋮ Unnamed Item ⋮ Comparing the notions of opacity for discrete-event systems ⋮ Unnamed Item ⋮ Reductions in circuit complexity: An isomorphism theorem and a gap theorem ⋮ Linear connectivity problems in directed hypergraphs ⋮ Domino-tiling games ⋮ Complexity of path discovery game problems ⋮ A note on context free languages, complexity classes, and diagonalization ⋮ Note on the complexity of Las Vegas automata problems ⋮ Bandwidth constraints on problems complete for polynomial time ⋮ The complexity of propositional linear temporal logics in simple cases ⋮ The complexity of two-player games of incomplete information ⋮ The relative power of logspace and polynomial time reductions ⋮ Complete problems for space bounded subclasses of NP
Cites Work
- On tape-bounded complexity classes and multihead finite automata
- Relationships between nondeterministic and deterministic tape complexities
- Theory of Formal Systems. (AM-47)
- State Reduction in Incompletely Specified Finite-State Machines
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Space-bounded reducibility among combinatorial problems
