scientific article; zbMATH DE number 3560737
From MaRDI portal
Publication:4131648
Cited in
(only showing first 100 items - show all)- On the complexity of typechecking top-down XML transformations
- On quantified propositional logics and the exponential time hierarchy
- A comparison of polynomial time reducibilities
- The polynomial hierarchy for some structures over the binary words
- Lower bound techniques for QBF expansion
- Interactive proofs and a Shamir-like result for real number computations
- Logics for unordered trees with data constraints
- Parsing Boolean grammars over a one-letter alphabet using online convolution
- Playing Savitch and cooking games
- Visibly linear temporal logic
- Three \(\sum^ P_ 2\)-complete problems in computational learning theory
- scientific article; zbMATH DE number 7559372 (Why is no real title available?)
- scientific article; zbMATH DE number 7559503 (Why is no real title available?)
- Complexity results for prefix grammars
- The complexity of pursuit on a graph
- One-nonterminal conjunctive grammars over a unary alphabet
- Inclusion Test Algorithms for One-Unambiguous Regular Expressions
- Learning residual alternating automata
- THE MODAL LOGIC OF STEPWISE REMOVAL
- On the complexity of timed pattern matching
- Initial-state detectability of stochastic discrete-event systems with probabilistic sensor failures
- State complexity of projection on languages recognized by permutation automata and commuting letters
- Feferman-vaught decompositions for prefix classes of first order logic
- Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
- Abduction from logic programs: Semantics and complexity
- Comparing the notions of opacity for discrete-event systems
- Reset complexity of ideal languages over a binary alphabet
- Simplifying XML schema: single-type approximations of regular tree languages
- Semantics and complexity of recursive aggregates in answer set programming
- Succinct representation of regular sets using gotos and Boolean variables
- On the bounded theories of finite trees
- Towards logical foundations for probabilistic computation
- Well-abstracted transition systems: Application to FIFO automata.
- Phutball is PSPACE-hard
- On classes of tractable unrestricted regular expressions
- The computational complexity of the satisfiability of modal Horn clauses for modal propositional logics
- Deciding equivalence of finite tree automata
- Frontiers of tractability for typechecking simple XML transformations
- Minimal NFA and biRFSA Languages
- On the complexity of propositional knowledge base revision, updates, and counterfactuals
- Satisfiability of Algebraic Circuits over Sets of Natural Numbers
- The (D)QBF preprocessor HQSpre -- underlying theory and its implementation
- On the complexity of formulas in semantic programming
- Complexity of unordered CNF games
- Decompositions of nondeterministic reductions
- On time-space classes and their relation to the theory of real addition
- Bounded repairability of word languages
- A Compact Representation for Syntactic Dependencies in QBFs
- A note on the complexity of \textbf{S4.2}
- Expansive automata networks
- Verifying polymer reaction networks using bisimulation
- A note on the space complexity of some decision problems for finite automata
- 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
- The complexity of logical theories
- Stable-unstable semantics: Beyond NP with normal logic programs
- On the complexity of kings
- Complexity of some problems in Petri nets
- Computational complexity of reversible reaction systems
- The complexity of synchronous notions of information flow security
- Generalizations of Opt P to the polynomial hierarchy
- Deciding determinism of unary languages
- Fast algorithms for revision of some special propositional knowledge bases
- The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
- Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)
- Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)
- Validating QBF Validity in HOL4
- Complexity of the multilevel critical node problem
- Minimizing finite automata is computationally hard
- Context-free grammars with lookahead
- Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
- scientific article; zbMATH DE number 7450037 (Why is no real title available?)
- Log space machines with multiple oracle tapes
- The complexity of two-player games of incomplete information
- Expressive capacity of subregular expressions
- Correcting a Space-Efficient Simulation Algorithm
- Bounding queries in the analytic polynomial-time hierarchy
- A covering system with least modulus 25
- Domino-tiling games
- The emptiness of complement problem for semi extended regular expressions requires \(c^n\) space
- Computing observers from observation policies in discrete-event systems
- Spanning the spectrum from safety to liveness
- On the minimization of XML schemas and tree automata for unranked trees
- On Boolean combinations forming piecewise testable languages
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Propositional dynamic logic of regular programs
- Some connections between bounded query classes and non-uniform complexity.
- Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
- New complexity results about Nash equilibria
- Topological network-control games
- A self-adaptive multi-engine solver for quantified Boolean formulas
- A complexity analysis of bisimilarity for value-passing processes
- On the complexity of finite, pushdown, and stack automata
- Succinctness of regular expressions with interleaving, intersection and counting
- Polynomial and abstract subrecursive classes
- Satisfiability of algebraic circuits over sets of natural numbers
- On the complexity of Boolean unification
- Equations over sets of integers with addition only
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)
