Search for dissertations about: "Peter Jonsson"

Showing result 11 - 15 of 28 swedish dissertations containing the words Peter Jonsson.

  2. 11. 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

  4. 12. 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

  5. 13. Constructing Algorithms for Constraint Satisfaction and Related Problems : Methods and Applications

    Author : Ola Angelsmark; Peter Jonsson; Brahim Hnich; Linköpings universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; constraint satisfaction; CSP; graph problems; algorithm construction; computational complexity; microstructures; graph colouring; decision problems; optimisation problems; quantum computing; molecular computing; Computer science; Datavetenskap;

    Abstract : In this thesis, we will discuss the construction of algorithms for solving Constraint Satisfaction Problems (CSPs), and describe two new ways of approaching them. Both approaches are based on the idea that it is sometimes faster to solve a large number of restricted problems than a single, large, problem. READ MORE

  6. 14. Exact Algorithms for Exact Satisfiability Problems

    Author : Vilhelm Dahllöf; Peter Jonsson; Fedor Fomin; Linköpings universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; NP-hardness; exact algorithms; satisfiability; exact satisfiability; Computer science; Datalogi;

    Abstract : This thesis presents exact means to solve a family of NP-hard problems. Starting with the well-studied Exact Satisfiability problem (XSAT) parents, siblings and daughters are derived and studied, each with interesting practical and theoretical properties. READ MORE

  7. 15. Exploiting Structure in CSP-related Problems

    Author : Tommy Färnqvist; Peter Jonsson; Miki Hermann; Linköpings universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES;

    Abstract : In this thesis we investigate the computational complexity and approximability of computational problems from the constraint satisfaction framework. An instance of a constraint satisfaction problem (CSP) has three components; a set V of variables, a set D of domain values, and a set of constraints C. READ MORE