Search for dissertations about: "COMPUTATIONAL-COMPLEXITY"

Showing result 1 - 5 of 225 swedish dissertations containing the word COMPUTATIONAL-COMPLEXITY.

2. 1. Computational Complexity of some Optimization Problems in Planning

   Author : Meysam Aghighi; Peter Jonsson; Christer Bäckström; Hector Geffner; Linköpings universitet; []
   Keywords : TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY;

   Abstract : Automated planning is known to be computationally hard in the general case. Propositional planning is PSPACE-complete and first-order planning is undecidable. One method for analyzing the computational complexity of planning is to study restricted subsets of planning instances, with the aim of differentiating instances with varying complexity. READ MORE

4. 2. A Study in the Computational Complexity of Temporal Reasoning

   Author : Mathias Broxvall; Peter Jonsson; Ulf Nilsson; Anders Haraldsson; Linköpings universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; temporal and spatial information; artificiell intelligens; algebra; tractable fragments; temporal formalisms; formalism STP; Computer science; Datavetenskap;

   Abstract : Reasoning about temporal and spatial information is a common task in computer science, especially in the field of artificial intelligence. The topic of this thesis is the study of such reasoning from a computational perspective. READ MORE

5. 3. Approximation and Online Algorithms with Applications in Computational Biology and Computational Geometry

   Author : Mia Persson; Data Vetenskap; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; numerisk analys; system; systems; control; Datalogi; numerical analysis; broadcasting; polygon exploration; robotics; Mathematics; Matematik; Computer science; clique partition; clustering; computational complexity; computational geometry; computational biology; online algorithm; kontroll; approximation algorithm;

   Abstract : The main contributions of this thesis are in the area of approximation and online algorithm design and derivation of lower bounds on the approximability for a number of combinatorial optimization problems with applications in computational biology and computational geometry. Approximation and online algorithms are fundamental tools used to deal with computationally hard problems and problems in which the input is gradually disclosed over time. READ MORE

6. 4. Consensus Algorithms for Trees and Strings

   Author : Jesper Jansson; Institutionen för datavetenskap; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; numerical analysis; computational complexity; Approximation algorithm; labeled tree; lowest common ancestor constraint; maximum agreement subtree; alignment between trees; clustering; Computer science; Hamming metric; systems; control; Datalogi; numerisk analys; system; kontroll;

   Abstract : This thesis studies the computational complexity and polynomial-time approximability of a number of discrete combinatorial optimization problems involving labeled trees and strings. The problems considered have applications to computational molecular biology, pattern matching, and many other areas of computer science. READ MORE

7. 5. Models and Complexity Results in Real-Time Scheduling Theory

   Author : Pontus Ekberg; Wang Yi; Alberto Marchetti-Spaccamela; Uppsala universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; Real-time systems; Scheduling theory; Task models; Computational complexity; Datavetenskap med inriktning mot inbyggda system; Computer Science with specialization in Embedded Systems;

   Abstract : When designing real-time systems, we want to prove that they will satisfy given timing constraints at run time. The main objective of real-time scheduling theory is to analyze properties of mathematical models that capture the temporal behaviors of such systems. READ MORE