scientific article; zbMATH DE number 3560737

zbMATH Open0359.68050MaRDI QIDQ4131648FDOQ4131648

Larry J. Stockmeyer, Albert R. Meyer

Publication date: 1973

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

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Turing machines and related notions (03D10) Word problems, etc. in computability and recursion theory (03D40)

Cited In (only showing first 100 items - show all)

On the complexity of typechecking top-down XML transformations
Visibly linear temporal logic
Three \(\sum^ P_ 2\)-complete problems in computational learning theory
Transformations into Normal Forms for Quantified Circuits
Initial-state detectability of stochastic discrete-event systems with probabilistic sensor failures
Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
Abduction from logic programs: Semantics and complexity
Deciding equivalence of finite tree automata
The computational complexity of the satisfiability of modal Horn clauses for modal propositional logics
Frontiers of tractability for typechecking simple XML transformations
On time-space classes and their relation to the theory of real addition
The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
A covering system with least modulus 25
Some connections between bounded query classes and non-uniform complexity.
Polynomial and abstract subrecursive classes
Satisfiability of algebraic circuits over sets of natural numbers
Efficient Probabilistically Checkable Debates
Ordered vertex removal and subgraph problems
Observations on the complexity of regular expression problems
The parallel complexity of finite-state automata problems
On coarser interval temporal logics
Gobang is PSPACE-complete
On the shortest path game
The most nonelementary theory
Computational complexity of winning strategies in two-person polynomial games
Is your model checker on time? On the complexity of model checking for timed modal logics
On the complexity of chess
An improved lower bound for the elementary theories of trees
Tree-size bounded alternation
On verification of D-detectability for discrete event systems
Descriptional and Computational Complexity of Finite Automata
The complexity of online manipulation of sequential elections
The complexity of node blocking for dags
Finite complete rewriting systems and the complexity of word problem
The set of realizations of a max-plus linear sequence is semi-polyhedral
Complexity of some problems concerningL systems
Equivalence problems for circuits over sets of natural numbers
PSPACE-Hardness of some combinatorial games
Observations on complete sets between linear time and polynomial time
Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete
Optimizing the region algebra is PSPACE-complete
The quantifier complexity of polynomial-size iterated definitions in first-order logic
The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic
On the complexity of the closed fragment of Japaridze's provability logic
Completeness and the finite model property for Kleene algebra, reconsidered
Playing Savitch and Cooking Games
Integer circuit evaluation is PSPACE-complete
Limitations of acyclic causal graphs for planning
The Analytic Polynomial-Time Hierarchy
Complexity of fixed-size bit-vector logics
Power indices and easier hard problems
On the complexity of LL(k) testing
Prohibiting repetitions makes playing games substantially harder
Fair simulation
Distributed XML design
Simulation relations and applications in formal methods
Space-bounded reducibility among combinatorial problems
Playing disjunctive sums is polynomial space complete
Decision algorithms for multiplayer noncooperative games of incomplete information
On termination and invariance for faulty channel machines
Practical verification of multi-agent systems against \textsc{Slk} specifications
Automata for unordered trees
Complexity of validity for propositional dependence logics
Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
Backtracking games and inflationary fixed points
The polynomial hierarchy for some structures over the binary words
Title not available (Why is that?)
A comparison of polynomial time reducibilities
Inclusion Test Algorithms for One-Unambiguous Regular Expressions
Parsing Boolean grammars over a one-letter alphabet using online convolution
The complexity of pursuit on a graph
One-nonterminal conjunctive grammars over a unary alphabet
Semantics and complexity of recursive aggregates in answer set programming
Simplifying XML schema: single-type approximations of regular tree languages
On classes of tractable unrestricted regular expressions
Phutball is PSPACE-hard
On the complexity of propositional knowledge base revision, updates, and counterfactuals
Bounded repairability of word languages
The complexity of logical theories
A note on the space complexity of some decision problems for finite automata
Nominal Kleene Coalgebra
Complexity of some problems in Petri nets
The complexity of synchronous notions of information flow security
Deciding determinism of unary languages
Minimizing finite automata is computationally hard
The complexity of two-player games of incomplete information
Domino-tiling games
On the minimization of XML schemas and tree automata for unranked trees
A linear-time algorithm for testing the truth of certain quantified Boolean formulas
Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
Propositional dynamic logic of regular programs
New complexity results about Nash equilibria
A self-adaptive multi-engine solver for quantified Boolean formulas
Succinctness of regular expressions with interleaving, intersection and counting
On the complexity of Boolean unification
Equations over sets of integers with addition only
Algorithms for Kleene algebra with converse
Lower bounds for multiplayer noncooperative games of incomplete information
Nondeterministic Tree Width of Regular Languages

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 Q4131648)