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)

Using decomposition-parameters for QBF: mind the prefix!
The expressiveness of looping terms in the semantic programming
A characterization of the power of vector machines
Incremental dead state detection in logarithmic time
Rational, recognizable, and aperiodic partially lossy queue languages
On Equations over Sets of Numbers and Their Limitations
The complexity of problems for quantified constraints
Note on the complexity of Las Vegas automata problems
Semicomputable points in Euclidean spaces
Antimirov and Mosses’s Rewrite System Revisited
Depletable channels: dynamics, behaviour, and efficiency in network design
Title not available (Why is that?)
Proving Valid Quantified Boolean Formulas in HOL Light
Interactive proofs and a Shamir-like result for real number computations
Title not available (Why is that?)
Title not available (Why is that?)
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 bounded theories of finite trees
Towards logical foundations for probabilistic computation
On the complexity of timed pattern matching
State complexity of projection on languages recognized by permutation automata and commuting letters
Succinct representation of regular sets using gotos and Boolean variables
Satisfiability of Algebraic Circuits over Sets of Natural Numbers
The (D)QBF preprocessor HQSpre -- underlying theory and its implementation
Complexity of unordered CNF games
A note on the complexity of \textbf{S4.2}
A Compact Representation for Syntactic Dependencies in QBFs
Decompositions of nondeterministic reductions
Computational complexity of reversible reaction systems
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
Validating QBF Validity in HOL4
Context-free grammars with lookahead
Complexity of the multilevel critical node problem
Correcting a Space-Efficient Simulation Algorithm
Log space machines with multiple oracle tapes
Topological network-control games
The emptiness of complement problem for semi extended regular expressions requires \(c^n\) space
On the complexity of finite, pushdown, and stack automata
Goodbye ioco
Solving projected model counting by utilizing treewidth and its limits
Complexity of universality and related problems for partially ordered NFAs
Monitoring first-order interval logic
Relativized polynomial hierarchies extending two levels
Non-elementary lower bound for Propositional Duration Calculus
Canonical models and the complexity of modal team logic
Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic
Solving Linear Equations in *-continuous Action Lattices
Solution complexity of local variants of sabotage game
Circuit satisfiability and constraint satisfaction around Skolem arithmetic
Circuit satisfiability and constraint satisfaction around Skolem arithmetic
On log-tape isomorphisms of complete sets
Super-Solutions
Recognition of properties of autonomous structural automata
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
On the complexity of robust multi-stage problems with discrete recourse
Testing containment of object-oriented conjunctive queries is ∏2p-hard
On the difference set of two transductions
Formal methods for NFA equivalence: QBFs, witness extraction, and encoding verification
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
On counting propositional logic and Wagner's hierarchy
The complexity of SORE-definability problems
Mean-payoff games with partial observation
A note on the complexity of program evaluation
Complexity-theoretic models of phase transitions in search problems
On the complexity of dataflow analysis of logic programs
Checking history-determinism is NP-hard for parity automata
Efficiently representing existential dependency sets for expansion-based QBF solvers
A logic for document spanners
Efficient implementation of regular languages using reversed alternating finite automata
Automata terms in a lazy \(\mathrm{WS}k\mathrm{S}\) decision procedure
Automata terms in a lazy \(\mathrm{WS}k\mathrm{S}\) decision procedure
An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning
Expressive completeness for LTL with modulo counting and group quantifiers
Schemas for unordered XML on a DIME
Beyond NP: quantifying over answer sets
Diophantine equations, Presburger arithmetic and finite automata
Title not available (Why is that?)
Balance problems for integer circuits
Balance problems for integer circuits
A general language-based framework for specifying and verifying notions of opacity
Motivating explanations in Bayesian networks using MAP-independence
Quantified Boolean Solving for Achievement Games
Short Presburger Arithmetic Is Hard
Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\)

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)