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)

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
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
Expressive completeness for LTL with modulo counting and group quantifiers
Title not available (Why is that?)
Schemas for unordered XML on a DIME
Distributed graph problems through an automata-theoretic Lens
Beyond NP: quantifying over answer sets
Diophantine equations, Presburger arithmetic and finite automata
Title not available (Why is that?)
Multi-linear iterative \(K\)-\(\Sigma\)-semialgebras.
Functions definable by arithmetic circuits
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
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
Short Presburger Arithmetic Is Hard
Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\)
Series which are both max-plus and min-plus rational are unambiguous
One-Nonterminal Conjunctive Grammars over a Unary Alphabet
NP completeness conditions for verifying the consistency of several kinds of systems of linear Diophantine discongruences

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)