scientific article; zbMATH DE number 3560737
From MaRDI portal
Publication:4131648
Cited in
(only showing first 100 items - show all)- A self-adaptive multi-engine solver for quantified Boolean formulas
- Backdoor sets of quantified Boolean formulas
- On self-reducibility and weak P-selectivity
- On the complexity of chess
- On classes of tractable unrestricted regular expressions
- PSPACE-Hardness of some combinatorial games
- The complexity of combinatorial problems with succinct input representation
- Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n) NSPACE( \,n)
- Succinct representation of regular sets using gotos and Boolean variables
- More complicated questions about maxima and minima, and some closures of NP
- Decompositions of nondeterministic reductions
- Non-elementary lower bound for Propositional Duration Calculus
- The emptiness of complement problem for semi extended regular expressions requires \(c^n\) space
- Complexity of Boolean algebras
- Hex ist Pspace-vollständig. (Hex is Pspace-complete)
- Tree-size bounded alternation
- Observations on the complexity of regular expression problems
- Optimization problems and the polynomial hierarchy
- Complexity of algorithms and computations
- On time-space classes and their relation to the theory of real addition
- Playing disjunctive sums is polynomial space complete
- The complexity of logical theories
- The complexity of computing the number of strings of given length in context-free languages
- A note on the space complexity of some decision problems for finite automata
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
- The parallel complexity of finite-state automata problems
- Computational complexity of winning strategies in two-person polynomial games
- A guide to completeness and complexity for modal logics of knowledge and belief
- Generalizations of Opt P to the polynomial hierarchy
- Some aspects of effectively constructive mathematics that are relevant to the foundations of neoclassical mathematical economics and the theory of games
- On the complexity of propositional knowledge base revision, updates, and counterfactuals
- On tape-bounded complexity classes and multihead finite automata
- Space-bounded reducibility among combinatorial problems
- A comparison of polynomial time reducibilities
- Polynomial and abstract subrecursive classes
- On the equivalence, containment, and covering problems for the regular and context-free languages
- A characterization of the power of vector machines
- The covering problem for linear context-free grammars
- Complete problems for deterministic polynomial time
- The polynomial-time hierarchy
- Complexity of some problems in Petri nets
- 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
- Bounding queries in the analytic polynomial-time hierarchy
- Sentences over integral domains and their computational complexities
- The computational complexity of the satisfiability of modal Horn clauses for modal propositional logics
- Separation of complexity classes in Koiran's weak model
- The complexity of PDL with interleaving
- Complexity of equivalence problems for concurrent systems of finite agents
- Abduction from logic programs: Semantics and complexity
- Well-abstracted transition systems: Application to FIFO automata.
- Fast algorithms for revision of some special propositional knowledge bases
- Some connections between bounded query classes and non-uniform complexity.
- A complexity analysis of bisimilarity for value-passing processes
- Efficient implementation of regular languages using reversed alternating finite automata
- Complexity-theoretic models of phase transitions in search problems
- Implementing automata. Selected papers from the 2nd international workshop, WIA '97, Univ. of Western Ontario, London, Ontario, Canada, September 18--20, 1997
- Decision algorithms for multiplayer noncooperative games of incomplete information
- The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
- On the complexity of formulas in semantic programming
- Computing observers from observation policies in discrete-event systems
- Spanning the spectrum from safety to liveness
- Practical verification of multi-agent systems against \textsc{Slk} specifications
- Problems on finite automata and the exponential time hypothesis
- Circuit satisfiability and constraint satisfaction around Skolem arithmetic
- Parameterized complexity of theory of mind reasoning in dynamic epistemic logic
- An extension-based approach to belief revision in abstract argumentation
- Model checking temporal properties of reaction systems
- An axiomatic semantics for \(\mathsf{ioco} \underline{\mathsf{s}}\) conformance relation
- Logic, semigroups and automata on words
- Domino-tiling games
- The complexity of the word problems for commutative semigroups and polynomial ideals
- 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
- Is your model checker on time? On the complexity of model checking for timed modal logics
- The complexity of first-order and monadic second-order logic revisited
- On the computational cost of disjunctive logic programming: Propositional case
- On termination and invariance for faulty channel machines
- The complexity of problems for quantified constraints
- Lower bound techniques for QBF expansion
- Expansive automata networks
- Verifying polymer reaction networks using bisimulation
- Complexity of universality and related problems for partially ordered NFAs
- 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
- From decidability to undecidability by considering regular sets of instances
- Comparing the notions of opacity for discrete-event systems
- On verification of D-detectability for discrete event systems
- Max-plus automata
- Descriptional complexity of regular languages
- Learning residual alternating automata
- 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
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)
