scientific article; zbMATH DE number 3555903

Cited in

(57)

A simple P-complete problem and its language-theoretic representations
The complexity of intersecting finite automata having few final states
[[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
\(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
The complexity of synchronizing Markov decision processes
Embedding arbitrary Boolean circuits into fungal automata
The word and generator problems for lattices
Matchstick puzzles on a grid
Positive versions of polynomial time
The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions
A recognition and parsing algorithm for arbitrary conjunctive grammars.
Tree-width and the monadic quantifier hierarchy.
Module checking
On computing graph closures
Parallelism and the feedback vertex set problem
Ordered vertex removal and subgraph problems
The monotone circuit value problem with bounded genus is in NC
Number of quantifiers is better than number of tape cells
How easy is local search?
Parallelism and the maximal path problem
The complexity of membership problems for circuits over sets of integers
The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
The complexity of circuit value and network stability
Properties that characterize LOGCFL
On the complexity of asynchronous freezing cellular automata
The complexity of agent design problems: Determinism and history dependence
The complexity of short two-person games
On short paths interdiction problems: Total and node-wise limited interdiction
Finding the closed partition of a planar graph
The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem
On the construction of parallel computers from various basis of Boolean functions
A theory of strict P-completeness
An introduction to parallelism in combinatorial optimization
Graph isomorphism, color refinement, and compactness
Balancing bounded treewidth circuits
A theory of strict P-completeness
On the complexity of the stability problem of binary freezing totalistic cellular automata
The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions
The binary network flow problem is logspace complete for P
Embedding arbitrary Boolean circuits into fungal automata
On the structure of solution-graphs for Boolean formulas
The maximum flow problem is log space complete for P
A P-complete graph partition problem
Games for active XML revisited
On the computational complexity of graph closures
Isomorphism of regular trees and words
Two dynamic programming algorithms for which interpreted pebbling helps
TANTRIX\(^{\text{TM}}\) rotation puzzles are intractable
Formal languages over GF(2)
Oracle branching programs and Logspace versus \(P^*\)
The complexity gap in the static analysis of cache accesses grows if procedure calls are added
Parallel evaluation of arithmetic circuits
Model checking and validity in propositional and modal inclusion logics
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
On the parameterized parallel complexity and the vertex cover problem
On the computational complexity of data flow analysis over finite bounded meet semilattices
A space efficient algorithm for the monotone planar circuit value problem

This page was built for publication:

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