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)

The complexity of PDL with interleaving
Emptiness problems for integer circuits
Emptiness problems for integer circuits
Isomorphism of regular trees and words
Distributed graph problems through an automata-theoretic lens
Some aspects of effectively constructive mathematics that are relevant to the foundations of neoclassical mathematical economics and the theory of games
Descriptional complexity of regular languages
Max-plus automata
Optimization problems and the polynomial hierarchy
Turing machines for dummies. Why representations do matter
The covering problem for linear context-free grammars
Sentences over integral domains and their computational complexities
Using decomposition-parameters for QBF: mind the prefix!
The expressiveness of looping terms in the semantic programming
Quantifier alternation for infinite words
Transducer descriptions of DNA code properties and undecidability of antimorphic problems
A characterization of the power of vector machines
Checking equivalences between concurrent systems of finite agents (extended abstract)
On Equations over Sets of Numbers and Their Limitations
The complexity of problems for quantified constraints
Semicomputable points in Euclidean spaces
Depletable channels: dynamics, behaviour, and efficiency in network design
Title not available (Why is that?)
Parameterized complexity of theory of mind reasoning in dynamic epistemic logic
Proving Valid Quantified Boolean Formulas in HOL Light
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
Interactive proofs and a Shamir-like result for real number computations
Lower bound techniques for QBF expansion
Logics for unordered trees with data constraints
Complexity results for prefix grammars
Feferman-vaught decompositions for prefix classes of first order logic
THE MODAL LOGIC OF STEPWISE REMOVAL
Reset complexity of ideal languages over a binary alphabet
Learning residual alternating automata
Title not available (Why is that?)
On the complexity of timed pattern matching
State complexity of projection on languages recognized by permutation automata and commuting letters
Comparing the notions of opacity for discrete-event systems
Succinct representation of regular sets using gotos and Boolean variables
Well-abstracted transition systems: Application to FIFO automata.
Satisfiability of Algebraic Circuits over Sets of Natural Numbers
Minimal NFA and biRFSA Languages
The (D)QBF preprocessor HQSpre -- underlying theory and its implementation
On the complexity of formulas in semantic programming
Decompositions of nondeterministic reductions
Stable-unstable semantics: Beyond NP with normal logic programs
Expansive automata networks
Verifying polymer reaction networks using bisimulation
Efficient enumeration of regular expressions for faster regular expression synthesis
Davis and Putnam meet Henkin: solving DQBF with resolution
Certified DQBF solving by definition extraction
A new 3-CNF transformation by parallel-serial graphs
On the complexity of kings
Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)
Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)
Generalizations of Opt P to the polynomial hierarchy
Title not available (Why is that?)
Fast algorithms for revision of some special propositional knowledge bases
Validating QBF Validity in HOL4
Context-free grammars with lookahead
Complexity of the multilevel critical node problem
Expressive capacity of subregular expressions
Correcting a Space-Efficient Simulation Algorithm
Log space machines with multiple oracle tapes
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
The emptiness of complement problem for semi extended regular expressions requires \(c^n\) space
On the complexity of finite, pushdown, and stack automata
A complexity analysis of bisimilarity for value-passing processes
Solving projected model counting by utilizing treewidth and its limits
Complexity of universality and related problems for partially ordered NFAs
Relativized polynomial hierarchies extending two levels
A formal methods approach to predicting new features of the eukaryotic vesicle traffic system
Non-elementary lower bound for Propositional Duration Calculus
Circuit satisfiability and constraint satisfaction around Skolem arithmetic
Circuit satisfiability and constraint satisfaction around Skolem arithmetic
On log-tape isomorphisms of complete sets
The robustness of LWPP and WPP, with an application to graph reconstruction
Super-Solutions
The robustness of LWPP and WPP, with an application to graph reconstruction
Counting problems for Parikh images
A Cookbook for Temporal Conceptual Data Modelling with Description Logics
Complexity of algorithms and computations
Typechecking top-down XML transformations: Fixed input or output schemas
Hardness of approximation for knapsack problems
Reinterpreting dependency schemes: soundness meets incompleteness in DQBF
Generalising automaticity to modal properties of finite structures
Limiting characterizations of low level space complexity classes
On the restricted equivalence for subclasses of propositional logic
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?)
Mean-payoff games with partial observation
A note on the complexity of program evaluation
Complexity-theoretic models of phase transitions in search problems
Ranking function synthesis for bit-vector relations

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)