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)

Title not available (Why is that?)
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
Nominal Kleene Coalgebra
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
Nondeterministic Tree Width of Regular Languages
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
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
Complete problems for deterministic polynomial time
The polynomial-time hierarchy
The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
More complicated questions about maxima and minima, and some closures of NP
Complexity of Boolean algebras
Dynamic Observers for the Synthesis of Opaque Systems
On self-reducibility and weak P-selectivity
Redundancy in logic. I: CNF propositional formulae
A guide to completeness and complexity for modal logics of knowledge and belief
On the decidability and complexity of problems for restricted hierarchical hybrid systems
On the complexity of some two-person perfect-information games
Hex ist Pspace-vollständig. (Hex is Pspace-complete)
Deciding whether a regular language is generated by a splicing system
The emptiness problem for intersections of regular languages
Minimizing nfa's and regular expressions
Logic, semigroups and automata on words
FLP answer set semantics without circular justifications for general logic programs
Descriptional and computational complexity of finite automata -- a survey
A framework for modular ERDF ontologies
Computational completeness of equations over sets of natural numbers
Latticed Simulation Relations and Games
Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
The complexity of the word problems for commutative semigroups and polynomial ideals
Automatic Proof Generation in Kleene Algebra
Weighted Bisimulation in Linear Algebraic Form
Compressing BMC encodings with QBF
Succinctness of pattern-based schema languages for XML
The complexity of first-order and monadic second-order logic revisited
Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
Relativization of questions about log space computability
An extension-based approach to belief revision in abstract argumentation
Complexity hierarchies beyond elementary
Extended RDF: computability and complexity issues
Five Determinisation Algorithms
Synthesis of Non-Interferent Timed Systems
Parity, circuits, and the polynomial-time hierarchy
The complexity of computing the number of strings of given length in context-free languages
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

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)