scientific article; zbMATH DE number 3555903

zbMATH Open0356.94042MaRDI QIDQ4128417FDOQ4128417

Authors: Leslie M. Goldschlager 

Publication date: 1977

Title of this publication is not available (Why is that?)

Mathematics Subject Classification ID

Turing machines and related notions (03D10)

Cited In (57)

• Embedding arbitrary Boolean circuits into fungal automata
• The complexity gap in the static analysis of cache accesses grows if procedure calls are added
• A simple P-complete problem and its language-theoretic representations
• The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\)
• The complexity of intersecting finite automata having few final states
• \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
• The complexity of synchronizing Markov decision processes
• Matchstick puzzles on a grid
• The word and generator problems for lattices
• 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
• The monotone circuit value problem with bounded genus is in NC
• Ordered vertex removal and subgraph problems
• 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
• On the complexity of asynchronous freezing cellular automata
• The complexity of agent design problems: Determinism and history dependence
• Properties that characterize LOGCFL
• 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
• Graph isomorphism, color refinement, and compactness
• A theory of strict P-completeness
• A theory of strict P-completeness
• An introduction to parallelism in combinatorial optimization
• Balancing bounded treewidth circuits
• Embedding arbitrary Boolean circuits into fungal automata
• 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
• On the structure of solution-graphs for Boolean formulas
• The binary network flow problem is logspace complete for P
• 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
• Formal languages over GF(2)
• Two dynamic programming algorithms for which interpreted pebbling helps
• TANTRIX\(^{\text{TM}}\) rotation puzzles are intractable
• Oracle branching programs and Logspace versus \(P^*\)
• Model checking and validity in propositional and modal inclusion logics
• Parallel evaluation of arithmetic circuits
• 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)