scientific article; zbMATH DE number 3560737
From MaRDI portal
Publication:4131648
Cited in
(only showing first 100 items - show all)- Space-bounded reducibility among combinatorial problems
- On the complexity of typechecking top-down XML transformations
- Tree-size bounded alternation
- On verification of D-detectability for discrete event systems
- Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
- Observations on complete sets between linear time and polynomial time
- The quantifier complexity of polynomial-size iterated definitions in first-order logic
- Integer circuit evaluation is PSPACE-complete
- Ordered vertex removal and subgraph problems
- Deciding equivalence of finite tree automata
- Frontiers of tractability for typechecking simple XML transformations
- Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete
- Observations on the complexity of regular expression problems
- Optimizing the region algebra is PSPACE-complete
- The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic
- Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
- Playing disjunctive sums is polynomial space complete
- Abduction from logic programs: Semantics and complexity
- Gobang is PSPACE-complete
- Complexity of some problems concerningL systems
- Descriptional and Computational Complexity of Finite Automata
- Polynomial and abstract subrecursive classes
- Playing Savitch and cooking games
- On the complexity of chess
- Fair simulation
- The complexity of node blocking for dags
- Decision algorithms for multiplayer noncooperative games of incomplete information
- Backtracking games and inflationary fixed points
- The parallel complexity of finite-state automata problems
- Equivalence problems for circuits over sets of natural numbers
- Visibly linear temporal logic
- Three \(\sum^ P_ 2\)-complete problems in computational learning theory
- A covering system with least modulus 25
- Satisfiability of algebraic circuits over sets of natural numbers
- Transformations into normal forms for quantified circuits
- On termination and invariance for faulty channel machines
- On the shortest path game
- The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
- Some connections between bounded query classes and non-uniform complexity.
- Practical verification of multi-agent systems against \textsc{Slk} specifications
- The Analytic Polynomial-Time Hierarchy
- The complexity of online manipulation of sequential elections
- Distributed XML design
- Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
- PSPACE-Hardness of some combinatorial games
- On time-space classes and their relation to the theory of real addition
- Automata for unordered trees
- Complexity of validity for propositional dependence logics
- Finite complete rewriting systems and the complexity of word problem
- Limitations of acyclic causal graphs for planning
- The set of realizations of a max-plus linear sequence is semi-polyhedral
- Power indices and easier hard problems
- On the complexity of LL(k) testing
- Prohibiting repetitions makes playing games substantially harder
- The computational complexity of the satisfiability of modal Horn clauses for modal propositional logics
- On the complexity of the closed fragment of Japaridze's provability logic
- Complexity of fixed-size bit-vector logics
- Simulation relations and applications in formal methods
- The polynomial hierarchy for some structures over the binary words
- Initial-state detectability of stochastic discrete-event systems with probabilistic sensor failures
- Computational complexity of winning strategies in two-person polynomial games
- An improved lower bound for the elementary theories of trees
- Is your model checker on time? On the complexity of model checking for timed modal logics
- Completeness and the finite model property for Kleene algebra, reconsidered
- On coarser interval temporal logics
- Efficient Probabilistically Checkable Debates
- The most nonelementary theory
- Lower bounds for multiplayer noncooperative games of incomplete information
- Descriptional and computational complexity of finite automata -- a survey
- On the complexity of some two-person perfect-information games
- Bounded repairability of word languages
- The complexity of computing the number of strings of given length in context-free languages
- Domino-tiling games
- Backdoors to satisfaction
- The complexity of first-order and monadic second-order logic revisited
- Dynamic Observers for the Synthesis of Opaque Systems
- A self-adaptive multi-engine solver for quantified Boolean formulas
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
- On the complexity of propositional knowledge base revision, updates, and counterfactuals
- On the computational complexity of assumption-based argumentation for default reasoning.
- The complexity of synchronous notions of information flow security
- A comparison of polynomial time reducibilities
- On classes of tractable unrestricted regular expressions
- Weighted Bisimulation in Linear Algebraic Form
- Extended RDF: computability and complexity issues
- Five Determinisation Algorithms
- Complexity of equations over sets of natural numbers
- Minimizing finite automata is computationally hard
- Succinctness of regular expressions with interleaving, intersection and counting
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- Kleene monads: handling iteration in a framework of generic effects
- Phutball is PSPACE-hard
- Compressing BMC encodings with QBF
- The big-O problem
- The complexity of logical theories
- A framework for modular ERDF ontologies
- Backdoor sets of quantified Boolean formulas
- More complicated questions about maxima and minima, and some closures of NP
- On the minimization of XML schemas and tree automata for unranked trees
- Deciding determinism of unary languages
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)
