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
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
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
Kleene monads: handling iteration in a framework of generic effects
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
The tractability frontier for NFA minimization
On the equivalence, containment, and covering problems for the regular and context-free languages
Complete sets and the polynomial-time hierarchy
CCS expressions, finite state processes, and three problems of equivalence
On the computational complexity of assumption-based argumentation for default reasoning.
Separation of complexity classes in Koiran's weak model
Model checking temporal properties of reaction systems
On the computational cost of disjunctive logic programming: Propositional case
Complexity of equivalence problems for concurrent systems of finite agents
Backdoors to satisfaction
Complexity of equations over sets of natural numbers
The big-O problem
Synchronous Kleene algebra
Synthesis of opaque systems with static and dynamic masks
Backdoor sets of quantified Boolean formulas
The complexity of membership problems for circuits over sets of integers
The complexity of combinatorial problems with succinct input representation
On tape-bounded complexity classes and multihead finite automata
Fair simulation

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)