scientific article; zbMATH DE number 3560737

zbMATH Open0359.68050MaRDI QIDQ4131648FDOQ4131648

Authors: Albert R. Meyer, Larry J. Stockmeyer

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)

Lower bound techniques for QBF expansion
Logics for unordered trees with data constraints
Complexity results for prefix grammars
Reset complexity of ideal languages over a binary alphabet
Learning residual alternating automata
Comparing the notions of opacity for discrete-event systems
Well-abstracted transition systems: Application to FIFO automata.
Minimal NFA and biRFSA Languages
On the complexity of formulas in semantic programming
Stable-unstable semantics: Beyond NP with normal logic programs
Expansive automata networks
Verifying polymer reaction networks using bisimulation
Title not available (Why is that?)
Fast algorithms for revision of some special propositional knowledge bases
Expressive capacity of subregular expressions
Bounding queries in the analytic polynomial-time hierarchy
On Boolean combinations forming piecewise testable languages
Computing observers from observation policies in discrete-event systems
Spanning the spectrum from safety to liveness
A complexity analysis of bisimilarity for value-passing processes
A formal methods approach to predicting new features of the eukaryotic vesicle traffic system
The robustness of LWPP and WPP, with an application to graph reconstruction
The robustness of LWPP and WPP, with an application to graph reconstruction
Hardness of approximation for knapsack problems
Reinterpreting dependency schemes: soundness meets incompleteness in DQBF
An axiomatic semantics for \(\mathsf{ioco} \underline{\mathsf{s}}\) conformance relation
Problems on finite automata and the exponential time hypothesis
Problems on finite automata and the exponential time hypothesis
Title not available (Why is that?)
Ranking function synthesis for bit-vector relations
Title not available (Why is that?)
Distributed graph problems through an automata-theoretic Lens
Multi-linear iterative \(K\)-\(\Sigma\)-semialgebras.
Functions definable by arithmetic circuits
From decidability to undecidability by considering regular sets of instances
Reasoning About Substructures and Games
Preprocessing for DQBF
Size, cost and capacity: a semantic technique for hard random QBFs
Characterization and complexity results on jumping finite automata
The recognition complexity of decidable theories
The complexity of PDL with interleaving
Isomorphism of regular trees and words
Distributed graph problems through an automata-theoretic lens
Descriptional complexity of regular languages
Max-plus automata
Quantifier alternation for infinite words
Checking equivalences between concurrent systems of finite agents (extended abstract)
Parameterized complexity of theory of mind reasoning in dynamic epistemic logic
Implementing automata. Selected papers from the 2nd international workshop, WIA '97, Univ. of Western Ontario, London, Ontario, Canada, September 18--20, 1997
On quantified propositional logics and the exponential time hierarchy
On the complexity of typechecking top-down XML transformations
Playing Savitch and cooking games
Visibly linear temporal logic
Three \(\sum^ P_ 2\)-complete problems in computational learning theory
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
Integer circuit evaluation is PSPACE-complete
Limitations of acyclic causal graphs for planning
Transformations into normal forms for quantified circuits
The Analytic Polynomial-Time Hierarchy

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)