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 49 for “"PSPACE-complete"”.
-
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 …
-
On the Complexity of Reconfiguration of Clique, Cluster Vertex Deletion, and Dominating Set
… is a vertex addition or deletion. For most NP-complete 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 …
-
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 …
-
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, …
-
Formal Methods in Computer-aided Design
… CAD flow encompasses an abundance of critical NP-complete and PSPACE-complete problems. Instead of developing a dedicated algorithm for each, the trend during the last decade has been to encode them in formal languages, such as Boolean satisfiability (SAT) and quantified Boolean formulas (QBFs), …
-
Clause Learning, Resolution Space, and Pebbling
Currently, the most effective complete SAT solvers are based on the DPLL algorithm augmented by Clause Learning. These solvers can handle many real-world problems from application areas like verification, diagnosis, planning, and design. Clause Learning works by storing previously computed, …
-
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 …
-
The Procedural Generation of Interesting Sokoban Levels
… which is computational interesting due to being PSPACE-complete. Beyond just generating levels, the question of whether or not the levels created by this algorithm are interesting to human players is explored. A study was carried out comparing player attention while playing hand made levels …
-
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 …
-
State minimization problems in finite state automata
… but the corresponding minimization problem is PSPACE-complete [2]. Even in the case of 2-MDFAs, which are only polynomially more succinct than DFAs, the minimization problem remains non-trivial; indeed, [3] shows that the corresponding decision problem is NP-complete. We are concerned with the …
-
On the relationship between satisfiability and partially observable Markov decision processes
… Markov decision processes (POMDPs) are all PSPACE-Complete problems. Since they are all complete for the same complexity class, I show how to convert them into one another in polynomial time and space. I discuss various properties of each encoding and how they get translated into equivalent …
-
Light On String Solving
… and design a decission procedure for a PSPACE-complete sub-theory. Additionally, we introduce a new benchmarking framework for string solvers and use it to showcase the power of our algorithms via an extensive empirical evaluation over a diverse set of benchmarks.
-
Interactions and Complexity in Multi-Agent Justification Logic
… Logic, as the corresponding modal systems are PSPACE-complete. We investigate the complexity of Justification Logic and Modal Logic when we allow multiple agents whose justifications affect each other -- by including some combination of the axioms t :iø → t :jø and t :iø → !t :j t :iø (modal …
-
Polynomial Timed Reductions to Solve Computer Security Problems in Access Control, Ethereum Smart Contract, Cloud VM Scheduling, and Logic Locking.
… timed reductions to 2 complexity classes: PSPACE-Complete and NP-Complete. This thesis is divided into 2 parts, problems reduced to: Model Checking (PSPACE-Complete) and Integer Linear Programming (ILP) (NP-Complete). The PSPACE-Complete problems are: Safety Analysis of Administrative …
-
Automated Safety Analysis of Administrative Temporal Role-Based Access Control (ATRBAC) Policies using Mohawk+T
… We first identify that the problem is PSPACE-complete. This is a much tighter identification of the computational complexity of the problem than prior work, which shows only that the problem is decidable. With this result as the basis, we propose an approach that leverages an existing …
-
The Expressive Power, Satisfiability and Path Checking Problems of MTL and TPTL over Non-Monotonic Data Words
… MTL and positive TPTL. Both of them are r.e.-complete. For existential TPTL and existential MTL, we show that SAT is NP-complete. We also investigate the complexity of path checking problems for TPTL and MTL over data words. These data words can be either finite or infinite periodic. For …
-
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, …
-
Membrane computing :The computational power of cP and water systems
… show for the rst time that cP systems can solve PSPACE complete problems in polynomial time (linear). We will also, demonstrate the advantages of our solution compared to other P system variants. Following this positive result, we demonstrate e cient solutions to NP-complete problems surpassing …
-
Practical reasoning and rule mining with DatalogMTL
… is, however, of high complexity, namely ExpSpace-complete and PSpace-complete with respect to data size, which makes reasoning in data-intensive applications challenging. Thus, theoretical research has focused on establishing a suitable trade-off between expressive power and complexity of …
-
Quantified Boolean Formulas: Proof Complexity and Models of Solving
… Boolean formulas (QBF), which form the canonical PSPACE-complete decision problem, are a decidable fragment of first-order logic. Any problem that can be solved within a polynomial-size space can be encoded succinctly as a QBF, including many concrete problems in computer science from domains such …
Page 1 of 3