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)

Linear connectivity problems in directed hypergraphs
Complete problems for space bounded subclasses of NP
An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines
Simultaneous (poly-time, log-space) lower bounds
Alternating multihead finite automata
Characterization of idempotent transformation monoids
Problems concerning fairness and temporal logic for conflict-free Petri nets
Tree-size bounded alternation
The complexity of decision problems for finite-turn multicounter machines
Number of quantifiers is better than number of tape cells
Symmetric space-bounded computation
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
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^*\)
The complexity of circuit value and network stability
A very hard log-space counting class
Polynomial and abstract subrecursive classes
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
Reductions in circuit complexity: An isomorphism theorem and a gap theorem
The relative power of logspace and polynomial time reductions
On path equivalence of nondeterministic finite automata
Counting quantifiers, successor relations, and logarithmic space
On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
A recognition and parsing algorithm for arbitrary conjunctive grammars.
Complexity of path discovery game problems
Hierarchical information and the synthesis of distributed strategies
Spanning the spectrum from safety to liveness
Balancing bounded treewidth circuits
On the computational complexity of problems related to distinguishability sets
On the descriptional complexity of stateless deterministic ordered restarting automata
Sorting, linear time and the satisfiability problem
Domino-tiling games
The complexity of propositional linear temporal logics in simple cases
Entanglement and the complexity of directed graphs
Complexity of universality and related problems for partially ordered NFAs
Comparing the notions of opacity for discrete-event systems
Equivalence classes and conditional hardness in massively parallel computations
Constrained synchronization and commutativity
Deciding definability by deterministic regular expressions
Concurrent reachability games
Prime languages
On linear languages recognized by deterministic biautomata
The complexity of searching implicit graphs
Investigations concerning the structure of complete sets
Inherent vacuity in lattice automata
Complexity of testing reachability in matroids
The role of rudimentary relations in complexity theory
Note on the complexity of Las Vegas automata problems
The Simple Reachability Problem in Switch Graphs
Descriptional and Computational Complexity of Finite Automata
Gradually intractable problems and nondeterministic log-space lower bounds
Classifying the computational complexity of problems
A note on context free languages, complexity classes, and diagonalization
Completeness for nondeterministic complexity classes
New problems complete for nondeterministic log space
Relativization of questions about log space computability
scientific article; zbMATH DE number 3576701 (Why is no real title available?)
The complexity of the membership problem for some extensions of context-free languagest†
Families of DFAs as acceptors of -regular languages
The complexity of searching succinctly represented graphs
Fifty years of the spectrum problem: survey and new results
Deciding determinism of regular languages
The complexity of properties of transformation semigroups
Automata that may change their mind
Partially ordered automata and piecewise testability
scientific article; zbMATH DE number 7439745 (Why is no real title available?)
scientific article; zbMATH DE number 7444007 (Why is no real title available?)
Rational, recognizable, and aperiodic partially lossy queue languages
Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers*
Typically-correct derandomization for small time and space
Multihead two-way probabilistic finite automata (extended abstract)
The emptiness problem for intersections of regular languages
scientific article; zbMATH DE number 7204396 (Why is no real title available?)
Simulations of unary one-way multi-head finite automata
Path-disruption games: bribery and a probabilistic model
The complexity of weakly recognizing morphisms
Infinite games with finite knowledge gaps
FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS
Two-way unary automata versus logarithmic space
Decision problems for convex languages
Descriptional and computational complexity of finite automata -- a survey
Investigations on automata and languages over a unary alphabet
Minimal and hyper-minimal biautomata
Descriptional complexity of iterated uniform finite-state transducers
Computational complexity of some problems involving congruences on algebras
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

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)