Space-bounded reducibility among combinatorial problems

Cites work

scientific article; zbMATH DE number 3455240 (Why is no real title available?)
scientific article; zbMATH DE number 3560737 (Why is no real title available?)
scientific article; zbMATH DE number 3557270 (Why is no real title available?)
scientific article; zbMATH DE number 3566230 (Why is no real title available?)
scientific article; zbMATH DE number 3571502 (Why is no real title available?)
scientific article; zbMATH DE number 3311755 (Why is no real title available?)
On tape-bounded complexity classes and multihead finite automata
Relationships between nondeterministic and deterministic tape complexities
State Reduction in Incompletely Specified Finite-State Machines
Theory of Formal Systems. (AM-47)

Cited in

(only showing first 100 items - show all)

Distributed XML design
Complexity of path discovery game problems
On the computational complexity of problems related to distinguishability sets
Decision problems for subregular classes
Decision problems for reversible and permutation automata
On the complexity of decision problems for parameterized finite state synchronous transducers
On the descriptional complexity of stateless deterministic ordered restarting automata
The Simple Reachability Problem in Switch Graphs
Relativization of questions about log space computability
Computational complexity of some problems involving congruences on algebras
An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines
On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
Rational, recognizable, and aperiodic partially lossy queue languages
Path-disruption games: bribery and a probabilistic model
Simulations of unary one-way multi-head finite automata
Typically-correct derandomization for small time and space
An automata-theoretic approach to linear temporal logic
Note on the complexity of Las Vegas automata problems
The isomorphism conjecture for constant depth reductions
scientific article; zbMATH DE number 7439745 (Why is no real title available?)
Completely distinguishable automata and the set of synchronizing words
FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS
Knapsack problems for NL
Linear connectivity problems in directed hypergraphs
Deciding definability by deterministic regular expressions
Infinite games with finite knowledge gaps
Prediction-preserving reducibility
Constrained synchronization and commutativity
The complexity of properties of transformation semigroups
Rewriting of regular expressions and regular path queries
Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers*
Symmetric space-bounded computation
Complete problems for space bounded subclasses of NP
On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
Comparing the notions of opacity for discrete-event systems
On inverse deterministic pushdown transductions
Reductions in circuit complexity: An isomorphism theorem and a gap theorem
Deciding determinism of regular languages
On languages specified by relative acceptance
Circuit complexity before the dawn of the new millennium
A very hard log-space counting class
Inherent vacuity in lattice automata
Simultaneous (poly-time, log-space) lower bounds
Counting quantifiers, successor relations, and logarithmic space
The role of rudimentary relations in complexity theory
A note on the space complexity of some decision problems for finite automata
New problems complete for nondeterministic log space
Infinity problems and countability problems for -automata
Descriptional complexity of iterated uniform finite-state transducers
Complexity of some problems in Petri nets
Decision problems for convex languages
On the equivalence of recursive and nonrecursive Datalog programs
A recognition and parsing algorithm for arbitrary conjunctive grammars.
Equivalence classes and conditional hardness in massively parallel computations
Minimizing finite automata is computationally hard
The complexity of two-player games of incomplete information
Domino-tiling games
Completeness for nondeterministic complexity classes
Hierarchical information and the synthesis of distributed strategies
Spanning the spectrum from safety to liveness
The complexity of the membership problem for some extensions of context-free languagest†
On the power of membrane dissolution in polarizationless P systems with active membranes
Characterization of idempotent transformation monoids
Polynomial and abstract subrecursive classes
The complexity of pure literal elimination
Prime languages
Fifty years of the spectrum problem: survey and new results
Complexity of universality and related problems for partially ordered NFAs
Number of quantifiers is better than number of tape cells
Complete sets and the polynomial-time hierarchy
Methods for proving completeness via logical reductions
Families of DFAs as acceptors of \(\omega\)-regular languages
On log-tape isomorphisms of complete sets
The complexity of propositional linear temporal logics in simple cases
scientific article; zbMATH DE number 7444007 (Why is no real title available?)
The complexity of searching implicit graphs
Entanglement and the complexity of directed graphs
Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs
On the complexity of topological sorting
Minimal and hyper-minimal biautomata
scientific article; zbMATH DE number 7204396 (Why is no real title available?)
Tree-size bounded alternation
Complete problems for deterministic polynomial time
The polynomial-time hierarchy
Descriptional and Computational Complexity of Finite Automata
Set augmented finite automata over infinite alphabets
Iterated stack automata and complexity classes
The relative power of logspace and polynomial time reductions
The complexity of circuit value and network stability
Alternating multihead finite automata
Investigations on automata and languages over a unary alphabet
Boundary sets of regular and context-free languages
On the computational complexity of satisfiability in propositional logics of programs
Unifiability is complete for co-N Log Space
On the complexity of some two-person perfect-information games
scientific article; zbMATH DE number 7350780 (Why is no real title available?)
A note on context free languages, complexity classes, and diagonalization
The complexity of searching succinctly represented graphs
The 2CNF Boolean formula satisfiability problem and the linear space hypothesis
Two-way unary automata versus logarithmic space

This page was built for publication: Space-bounded reducibility among combinatorial problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1221749)