scientific article; zbMATH DE number 3560737
From MaRDI portal
zbMath0359.68050MaRDI QIDQ4131648
Albert R. Meyer, Larry J. Stockmeyer
Publication date: 1973
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Word problems, etc. in computability and recursion theory (03D40) Turing machines and related notions (03D10)
Related Items
The complexity of synchronous notions of information flow security, On the complexity of timed pattern matching, State complexity of projection on languages recognized by permutation automata and commuting letters, On the complexity of Boolean unification, Equations over sets of integers with addition only, PSPACE-Hardness of some combinatorial games, The complexity of combinatorial problems with succinct input representation, Algorithms for Kleene algebra with converse, Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\), On the complexity of kings, Succinct representation of regular sets using gotos and Boolean variables, On the decidability and complexity of problems for restricted hierarchical hybrid systems, More complicated questions about maxima and minima, and some closures of NP, Decompositions of nondeterministic reductions, Deciding whether a regular language is generated by a splicing system, The complexity of membership problems for circuits over sets of integers, A framework for modular ERDF ontologies, The most nonelementary theory, Frontiers of tractability for typechecking simple XML transformations, On the minimization of XML schemas and tree automata for unranked trees, Non-elementary lower bound for Propositional Duration Calculus, Simplifying XML schema: single-type approximations of regular tree languages, The emptiness of complement problem for semi extended regular expressions requires \(c^n\) space, Bounded repairability of word languages, The complexity of node blocking for dags, Complexity of Boolean algebras, Hex ist Pspace-vollständig. (Hex is Pspace-complete), Phutball is PSPACE-hard, Deciding determinism of unary languages, The tractability frontier for NFA minimization, Tree-size bounded alternation, Observations on complete sets between linear time and polynomial time, Observations on the complexity of regular expression problems, Optimization problems and the polynomial hierarchy, Schemas for unordered XML on a DIME, Extended RDF: computability and complexity issues, Complexity of equations over sets of natural numbers, Complexity of algorithms and computations, On time-space classes and their relation to the theory of real addition, One-nonterminal conjunctive grammars over a unary alphabet, Playing disjunctive sums is polynomial space complete, The complexity of logical theories, CCS expressions, finite state processes, and three problems of equivalence, Synthesis of opaque systems with static and dynamic masks, Distributed XML design, New complexity results about Nash equilibria, The complexity of computing the number of strings of given length in context-free languages, On the complexity of the closed fragment of Japaridze's provability logic, Typechecking top-down XML transformations: Fixed input or output schemas, A note on the space complexity of some decision problems for finite automata, Limitations of acyclic causal graphs for planning, The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems, The parallel complexity of finite-state automata problems, The complexity of pursuit on a graph, Computational complexity of winning strategies in two-person polynomial games, Complexity of fixed-size bit-vector logics, A guide to completeness and complexity for modal logics of knowledge and belief, Generalizations of Opt P to the polynomial hierarchy, Visibly linear temporal logic, Some aspects of effectively constructive mathematics that are relevant to the foundations of neoclassical mathematical economics and the theory of games, Complexity of validity for propositional dependence logics, Automata for unordered trees, Three \(\sum^ P_ 2\)-complete problems in computational learning theory, On the complexity of propositional knowledge base revision, updates, and counterfactuals, Succinctness of pattern-based schema languages for XML, Semantics and complexity of recursive aggregates in answer set programming, On tape-bounded complexity classes and multihead finite automata, Minimizing finite automata is computationally hard, Descriptional and computational complexity of finite automata -- a survey, A new 3-CNF transformation by parallel-serial graphs, On the complexity of typechecking top-down XML transformations, Space-bounded reducibility among combinatorial problems, A comparison of polynomial time reducibilities, Synchronous Kleene algebra, Polynomial and abstract subrecursive classes, Succinctness of regular expressions with interleaving, intersection and counting, Parsing Boolean grammars over a one-letter alphabet using online convolution, On the equivalence, containment, and covering problems for the regular and context-free languages, The set of realizations of a max-plus linear sequence is semi-polyhedral, A characterization of the power of vector machines, The covering problem for linear context-free grammars, Satisfiability of algebraic circuits over sets of natural numbers, Complete problems for deterministic polynomial time, Ordered vertex removal and subgraph problems, The polynomial-time hierarchy, Complexity of some problems in Petri nets, On the shortest path game, A self-adaptive multi-engine solver for quantified Boolean formulas, Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete, Optimizing the region algebra is PSPACE-complete, Backdoor sets of quantified Boolean formulas, Finite complete rewriting systems and the complexity of word problem, Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories, On self-reducibility and weak P-selectivity, On the complexity of chess, On the complexity of LL(k) testing, Prohibiting repetitions makes playing games substantially harder, The complexity of two-player games of incomplete information, On classes of tractable unrestricted regular expressions, Backtracking games and inflationary fixed points, Nominal Kleene Coalgebra, Preprocessing for DQBF, Unnamed Item, Backdoors to Satisfaction, Weighted Bisimulation in Linear Algebraic Form, THE MODAL LOGIC OF STEPWISE REMOVAL, Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic, Unnamed Item, Short Presburger Arithmetic Is Hard, Rational, recognizable, and aperiodic partially lossy queue languages, THE RECOGNITION COMPLEXITY OF DECIDABLE THEORIES, Super-Solutions, A Cookbook for Temporal Conceptual Data Modelling with Description Logics, Deciding equivalence of finite tree automata, The emptiness problem for intersections of regular languages, Unnamed Item, Solving Linear Equations in *-continuous Action Lattices, Automatic Proof Generation in Kleene Algebra, Monitoring first-order interval logic, Unnamed Item, Testing containment of object-oriented conjunctive queries is ∏2p-hard, Stable-unstable semantics: Beyond NP with normal logic programs, Reasoning About Substructures and Games, Beyond NP: Quantifying over Answer Sets, Latticed Simulation Relations and Games, Correcting a Space-Efficient Simulation Algorithm, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Quirky Quantifiers: Optimal Models and Complexity of Computation Tree Logic, Transformations into Normal Forms for Quantified Circuits, A note on the complexity of S4.2, Isomorphism of Regular Trees and Words, An improved lower bound for the elementary theories of trees, Relativization of questions about log space computability, Parity, circuits, and the polynomial-time hierarchy, A note on the complexity of program evaluation, Complexity results for prefix grammars, Functions Definable by Arithmetic Circuits, On the complexity of finite, pushdown, and stack automata, Efficiently Representing Existential Dependency Sets for Expansion-based QBF Solvers, Fair simulation, Relativized polynomial hierarchies extending two levels, Multi-Linear Iterative K-Σ-Semialgebras, Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages, Power indices and easier hard problems, Playing Savitch and Cooking Games, Lower bounds for multiplayer noncooperative games of incomplete information, Unnamed Item, Unnamed Item, Unnamed Item, A covering system with least modulus 25, Unnamed Item, Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity, Antimirov and Mosses’s Rewrite System Revisited, Five Determinisation Algorithms, Unnamed Item, Integer circuit evaluation is PSPACE-complete, The quantifier complexity of polynomial-size iterated definitions in first-order logic, On the complexity of dataflow analysis of logic programs, Checking equivalences between concurrent systems of finite agents (Extended abstract), Reset Complexity of Ideal Languages Over a Binary Alphabet, Descriptional and Computational Complexity of Finite Automata, Satisfiability of Algebraic Circuits over Sets of Natural Numbers, Automata terms in a lazy \(\mathrm{WS}k\mathrm{S}\) decision procedure, Automata terms in a lazy \(\mathrm{WS}k\mathrm{S}\) decision procedure, Series which are both max-plus and min-plus rational are unambiguous, Unnamed Item, Minimal NFA and biRFSA Languages, Recognition of properties of autonomous structural automata, Canonical Models and the Complexity of Modal Team Logic, Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\), Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\), An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning, Complexity of some problems concerningL systems, Validating QBF Validity in HOL4, Proving Valid Quantified Boolean Formulas in HOL Light, Efficient Probabilistically Checkable Debates, Expressive capacity of subregular expressions, A Compact Representation for Syntactic Dependencies in QBFs, On Equations over Sets of Numbers and Their Limitations, One-Nonterminal Conjunctive Grammars over a Unary Alphabet, Semicomputable points in Euclidean spaces, Dynamic Observers for the Synthesis of Opaque Systems, Synthesis of Non-Interferent Timed Systems, Counting problems for parikh images, Emptiness Problems for Integer Circuits, Nondeterministic Tree Width of Regular Languages, Unnamed Item, Note on the complexity of Las Vegas automata problems, Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?, The polynomial hierarchy for some structures over the binary words, Inclusion Test Algorithms for One-Unambiguous Regular Expressions, The Analytic Polynomial-Time Hierarchy, The (D)QBF Preprocessor HQSpre – Underlying Theory and Its Implementation1, On the restricted equivalence for subclasses of propositional logic, Limiting characterizations of low level space complexity classes, Diophantine equations, Presburger arithmetic and finite automata, On Boolean combinations forming piecewise testable languages, Complexity of the multilevel critical node problem, On the complexity of formulas in semantic programming, The computational complexity of the satisfiability of modal Horn clauses for modal propositional logics, Kleene Monads: Handling Iteration in a Framework of Generic Effects, Turing Machines for Dummies, Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete, Separation of complexity classes in Koiran's weak model, Computing observers from observation policies in discrete-event systems, The complexity of first-order and monadic second-order logic revisited, Spanning the spectrum from safety to liveness, Generalising automaticity to modal properties of finite structures, Practical verification of multi-agent systems against \textsc{Slk} specifications, The complexity of PDL with interleaving, Mean-payoff games with partial observation, The complexity of online manipulation of sequential elections, Minimizing nfa's and regular expressions, Problems on finite automata and the exponential time hypothesis, NP completeness conditions for verifying the consistency of several kinds of systems of linear Diophantine discongruences, Initial-state detectability of stochastic discrete-event systems with probabilistic sensor failures, Complexity of equivalence problems for concurrent systems of finite agents, Circuit satisfiability and constraint satisfaction around Skolem arithmetic, On the computational cost of disjunctive logic programming: Propositional case, Emptiness problems for integer circuits, Abduction from logic programs: Semantics and complexity, A general language-based framework for specifying and verifying notions of opacity, Motivating explanations in Bayesian networks using MAP-independence, Solving projected model counting by utilizing treewidth and its limits, Depletable channels: dynamics, behaviour, and efficiency in network design, Logics for unordered trees with data constraints, Well-abstracted transition systems: Application to FIFO automata., On termination and invariance for faulty channel machines, Distributed graph problems through an automata-theoretic lens, Transducer descriptions of DNA code properties and undecidability of antimorphic problems, Fast algorithms for revision of some special propositional knowledge bases, Parameterized complexity of theory of mind reasoning in dynamic epistemic logic, The complexity of problems for quantified constraints, Some connections between bounded query classes and non-uniform complexity., An extension-based approach to belief revision in abstract argumentation, FLP answer set semantics without circular justifications for general logic programs, Redundancy in logic. I: CNF propositional formulae, Context-free grammars with lookahead, Lower bound techniques for QBF expansion, Model checking temporal properties of reaction systems, Ranking function synthesis for bit-vector relations, Computational completeness of equations over sets of natural numbers, Expansive automata networks, Verifying polymer reaction networks using bisimulation, Complexity of universality and related problems for partially ordered NFAs, Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth, Equivalence problems for circuits over sets of natural numbers, 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, An axiomatic semantics for \(\mathsf{ioco} \underline{\mathsf{s}}\) conformance relation, Complete sets and the polynomial-time hierarchy, Log space machines with multiple oracle tapes, On the complexity of some two-person perfect-information games, On log-tape isomorphisms of complete sets, A linear-time algorithm for testing the truth of certain quantified Boolean formulas, Gobang is PSPACE-complete, Propositional dynamic logic of regular programs, Quantifier Alternation for Infinite Words, Using decomposition-parameters for QBF: mind the prefix!, The expressiveness of looping terms in the semantic programming, Logic, semigroups and automata on words, Expressive Completeness for LTL With Modulo Counting and Group Quantifiers, From decidability to undecidability by considering regular sets of instances, Comparing the notions of opacity for discrete-event systems, Bounding queries in the analytic polynomial-time hierarchy, Complexity Hierarchies beyond Elementary, On verification of D-detectability for discrete event systems, Problems on Finite Automata and the Exponential Time Hypothesis, Domino-tiling games, Max-plus automata, Descriptional complexity of regular languages, On coarser interval temporal logics, Sentences over integral domains and their computational complexities, A logic for document spanners, Interactive proofs and a Shamir-like result for real number computations, Reinterpreting dependency schemes: soundness meets incompleteness in DQBF, A complexity analysis of bisimilarity for value-passing processes, Efficient implementation of regular languages using reversed alternating finite automata, The complexity of the word problems for commutative semigroups and polynomial ideals, Complexity-theoretic models of phase transitions in search problems, Balance problems for integer circuits, Implementing automata. Selected papers from the 2nd international workshop, WIA '97, Univ. of Western Ontario, London, Ontario, Canada, September 18--20, 1997, On the computational complexity of assumption-based argumentation for default reasoning., Fair simulation, The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic, Compressing BMC Encodings with QBF, Is your model checker on time? On the complexity of model checking for timed modal logics, Hardness of approximation for knapsack problems, Learning residual alternating automata, Decision algorithms for multiplayer noncooperative games of incomplete information, Efficient enumeration of regular expressions for faster regular expression synthesis, Distributed graph problems through an automata-theoretic Lens, Davis and Putnam meet Henkin: solving DQBF with resolution, Certified DQBF solving by definition extraction, The presence of a zero in an integer linear recurrent sequence is NP-hard to decide, Characterization and complexity results on jumping finite automata, On counting propositional logic and Wagner's hierarchy, OuterCount: a first-level solution-counter for quantified Boolean formulas, Simulation relations and applications in formal methods, Feferman-vaught decompositions for prefix classes of first order logic, Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic, Computational complexity of reversible reaction systems, Formal methods for NFA equivalence: QBFs, witness extraction, and encoding verification, Goodbye ioco, Completeness and the finite model property for Kleene algebra, reconsidered, On the complexity of robust multi-stage problems with discrete recourse
