Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 20 of 102 for “"PSPACE"”.

  1. Evaluating conjunctive and graph queries over the EL profile of OWL 2

    … in OWL 2 EL and show that the problem is PSpace-complete in combined complexity, the complexity measured in the total size of the input. All the previously known approaches encode the regular role inclusions using finite automata that can be worst-case exponential in size, and thus are not …

    oxford Repository record for Evaluating conjunctive and graph queries over the EL profile of OWL 2 (opens in a new tab)

  2. Empirical Research into the Intractability of Finite State Machines

    … has established that State Verification is a PSPACE-complete problem, but the proof did not provide an empirical verification. A primary objective of this research is to provide the empirical evidence to support the theoretic proof that the State Verification problem is PSPACE-complete. A …

    texas-state Repository record for Empirical Research into the Intractability of Finite State Machines (opens in a new tab)

  3. Relations between Space-Bounded and Adaptive Massively Parallel Computations

    … We establish that it is unlikely that $\PSPACE$ admits $\AMPC$ algorithms, even with polynomially many rounds. We also establish that showing $\PSPACE$ is a subclass of (nonuniform) $\AMPC$ with polynomially many rounds leads to a significant separation result in complexity theory, namely …

    iastate Repository record for Relations between Space-Bounded and Adaptive Massively Parallel Computations (opens in a new tab)

  4. Algorithmic randomness and analysis

    … space computability in R^n to define weakly pspace-random points, a new variant of polynomial space randomness. We show that the Lebesgue differentiation theorem characterizes weakly pspace random points. That is, a point x is weakly pspace random if and only if the Lebesgue differentiation …

    iastate Repository record for Algorithmic randomness and analysis (opens in a new tab)

  5. On the Complexity of Reconfiguration of Clique, Cluster Vertex Deletion, and Dominating Set

    … problems, this problem has been shown to be PSPACE-complete, while for some problems in P, this problem could be either in P or PSPACE-complete. However, knowing the complexity of a decision problem does not directly imply the complexity of its st-connectivity problem. Therefore, it is …

    waterloo Repository record for On the Complexity of Reconfiguration of Clique, Cluster Vertex Deletion, and Dominating Set (opens in a new tab)

  6. Kolmogorov extraction and resource-bounded zero-one laws

    … Our results include: (i) If Dim[subscript pspace](E)> 0, then Dim[subscript pspace](E/O(l)) = 1. (ii) Dim(E/O(l) l ESPACE) is either 0 or 1. (iii) Dim(E/poly l ESPACE) is either 0 or 1. (iv) Either Dim[superscript (1) over subscript psspace](E/O(n)) = 0 or Dim[superscript ( -1) over …

    iastate Repository record for Kolmogorov extraction and resource-bounded zero-one laws (opens in a new tab)

  7. Complexity cores in average-case complexity theory

    … exist for complexity classes such as EXP and PSPACE.</p> <p>This worst-case to average-case connections for classes such as EXP and</p> <p>PSPACE are obtained via random self-reductions. There is evidence that</p> <p>techniques used to obtain worst-case to average-case connections for EXP …

    iastate Repository record for Complexity cores in average-case complexity theory (opens in a new tab)

  8. Automata Linear Dynamic Logic on Finite Traces

    … First-Order Logic and satisfiability for LTL is PSPACE-complete. Linear Dynamic Logic (LDL), another temporal logic, is equivalent to Monadic Second-Order Logic, but its method of satisfiability checking cannot be applied to a nontrivial subset of LDL formulas. In this thesis I introduce Automata …

    rice Repository record for Automata Linear Dynamic Logic on Finite Traces (opens in a new tab)

  9. To and Fro Between Tableaus and Automata for Description Logics

    … fuer Implementierungen und fuer den Nachweis von PSPACE- und NEXPTIME-Resultaten, waehrend Automaten sich besonders fuer EXPTIME-Resultate anbieten. Zudem ermoeglichen sie eine vom Standpunkt der Theorie aus elegantere Handhabung von unendlichen Strukturen, eignen sich aber wesentlich schlechter …

    qucosa-diss

  10. Computing Winning Strategies for Poset Games

    … winning strategies for the game of Chomp is in PSPACE. \Ne also present the idea of "Game Completeness", and give an overview of efforts to translate any poset game into an equivalent configuration of Chomp. Finally, we show how Skelley's bounded arithmetic theory W<sup>1</sup><sub>1</sub> can …

    mcmaster Repository record for Computing Winning Strategies for Poset Games (opens in a new tab)

  11. A study of one-turn quantum refereed games

    … the best known upper bound on QRG(1) was PSPACE. We have proved that if one of the provers is completely classical, sending a classical probability distribution instead of a quantum state, the new class, which we name CQRG(1), is contained in Ǝ · PP (non- deterministic polynomial-time …

    waterloo Repository record for A study of one-turn quantum refereed games (opens in a new tab)

  12. Solving moving-blocks problems

    … of the cases proving that these problems are PSPACE-complete. We consider two sets of problems: PULL moves only, and PUSH and PULL moves combined. Our reductions are from Nondeterministic Constraint Logic. We prove that many problems with PULL moves only are PSPACE-complete. In addition, we …

    brazil-ufrgs Repository record for Solving moving-blocks problems (opens in a new tab)

  13. On the Descriptive Complexity and Ramsey Measure of Sets of Oracles Separating Common Complexity Classes

    … famously in 1992 with the result that IP equals PSPACE, in spite of the classes being shown unequal with probability 1. Here, we propose what could be considered strengthening of the random oracle hypothesis, using a stricter notion of what it means for a set to be 'large'. In particular, we …

    unt Repository record for On the Descriptive Complexity and Ramsey Measure of Sets of Oracles Separating Common Complexity Classes (opens in a new tab)

  14. Applications of Games to Propositional Proof Complexity

    … as various resources. These results include the PSPACE-Completeness of Tree Resolution clause space (and the Prover/Delayer game), the PSPACE-Completeness of Input Resolution derivation total space, and the PSPACE-Hardness of Resolution variable space. This research has theoretical as well as …

    toronto-retro Repository record for Applications of Games to Propositional Proof Complexity (opens in a new tab)

  15. Proof Complexity for Quantified Boolean Formulas

    … Deciding whether a QBF is true or false is PSPACE-complete and a wide range of mathematical and industrial problems can be expressed as QBFs. QBF proof complexity is the theoretical analysis of algorithmic techniques for solving QBFs. We make a detailed comparison of the proof systems Q-Res, …

    whiterose Download PDF for Proof Complexity for Quantified Boolean Formulas (opens in a new tab)

  16. Inkrementální induktivní pokrytelnost pro alternující konečné automaty

    … Aj keď je známe, že problém je sám o sebe PSpace-ťažký, zameriavame sa na to, aby bolo rozhodovanie prázdnosti výpočetne prijateľné v niektorých triedach automatov s praktickým využitím. Dosiahli sme niekoľko zaujímavýcch výsledkov v porovnaní so špičkovými algoritmami, predovšetkým v …

    brno-tech Repository record for Inkrementální induktivní pokrytelnost pro alternující konečné automaty (opens in a new tab)

  17. Locality and Complexity in Quantum Information Dynamics

    … not observables equilibrate to a givenvalue is PSPACE-complete. We also show that deciding whether observables relax to the thermal equilibrium value is contained in PSPACE, and is PSPACE-hard under quantum polynomial time reductions. These problems are thus intractable even for a quantum …

    maryland Repository record for Locality and Complexity in Quantum Information Dynamics (opens in a new tab)

  18. Exploiting Problem Structure in QBF Solving

    … Quantified Boolean Formula (QBF) is a canonical PSPACE-complete problem. It provides a powerful framework for encoding problems that lie in PSPACE. These include many problems in automatic verification, and problems with discrete uncertainty or non-determinism. Two person adversarial games are …

    toronto-retro Repository record for Exploiting Problem Structure in QBF Solving (opens in a new tab)

  19. Distance Desert Automata and Star Height Substitutions

    … of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in 22O(n2) space whether the language accepted by an n-state non-deterministic automaton is of a star height less than a given integer h (concerning rational expressions with union, …

    qucosa-diss

Page 1 of 6