Space-bounded reducibility among combinatorial problems

From MaRDI portal

Publication:1221749

Jump to:navigation, search

DOI10.1016/S0022-0000(75)80050-XzbMath0317.02039OpenAlexW1989887898MaRDI QIDQ1221749

Neil D. Jones

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computability and recursion theory (03D99) Turing machines and related notions (03D10)

Related Items

Rational, recognizable, and aperiodic partially lossy queue languages, Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers*, The emptiness problem for intersections of regular languages, Set augmented finite automata over infinite alphabets, Completely distinguishable automata and the set of synchronizing words, The 2CNF Boolean formula satisfiability problem and the linear space hypothesis, Weakly and Strongly Irreversible Regular Languages, On the power of membrane dissolution in polarizationless P systems with active membranes, Complexity of exclusive nondeterministic finite automata, Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs, Unnamed Item, SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA, Investigations on Automata and Languages Over a Unary Alphabet, Computational complexity of some problems involving congruences on algebras, Minimal and Hyper-Minimal Biautomata, Descriptional complexity of iterated uniform finite-state transducers, Unnamed Item, Multihead two-way probabilistic finite automata, The complexity of weakly recognizing morphisms, Typically-correct derandomization for small time and space, FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS, 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

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1221749&oldid=13297419"