Sökning: "Parameterized complexity"

Visar resultat 1 - 5 av 31 avhandlingar innehållade orden Parameterized complexity.

  1. 1. Complexity Dichotomies for CSP-related Problems

    Författare :Gustav Nordh; Peter Jonsson; Andrei Krokhin; Linköpings universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Complexity; Constraint Satisfaction Problem; System of Equations; Nonmonotonic Logic; Circumscription; Abduction; Isomorphism; Computer science; Datavetenskap;

    Sammanfattning : Ladner’s theorem states that if P ≠ NP, then there are problems in NP that are neither in P nor NP-complete. Csp(Γ) is a class of problems containing many well-studied combinatorial problems in NP. LÄS MER

  3. 2. Complexity and expressiveness for formal structures in Natural Language Processing

    Författare :Petter Ericson; Henrik Björklund; Frank Drewes; Umeå universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; graph grammars; formal languages; natural language processing; parameterized complexity; abstract meaning representation; tree automata; deterministic tree-walking transducers; mildly context-sensitive languages; hyperedge replacement; tree adjoining languages; minimally adequate teacher;

    Sammanfattning : The formalized and algorithmic study of human language within the field of Natural Language Processing (NLP) has motivated much theoretical work in the related field of formal languages, in particular the subfields of grammar and automata theory. Motivated and informed by NLP, the papers in this thesis explore the connections between expressibility – that is, the ability for a formal system to define complex sets of objects – and algorithmic complexity – that is, the varying amount of effort required to analyse and utilise such systems. LÄS MER

  4. 3. Parameterized algorithms for hitting set variants applied to protein identification in shotgun proteomics

    Författare :Leonid Molokov; Chalmers tekniska högskola; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; Union Editing; Fixed Parameter Tractable; Shotgun proteomics; Hitting Set; Parameterized complexity; Hypergraph; Set Cover;

    Sammanfattning : This work is dedicated to problem of protein identification in bottom-up proteomics, and in particular, in shotgun proteomics. It is aimed on providing a new way of interpretation of peak lists. LÄS MER

  5. 4. Protein Mixture Inference as Hitting Set Variants and Linear Algebra Problems

    Författare :Leonid Molokov; Chalmers tekniska högskola; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; Union Editing; Shotgun proteomics; Parameterized complexity; Protein Inference; Shared Peptides; Set Cover; Hypergraph; Hitting Set; Fixed Parameter Tractable; Protein Quan- ti; Star Editing;

    Sammanfattning : This work is dedicated to the problems of protein inference and quantification in bottom-up proteomics, and, in particular, in shotgun proteomics. We adopt a rather classical approach of representing inference problem as a set cover, where proteins are understood as sets of their observations: peptides' masses or sequences. LÄS MER

  7. 5. Computational Complexity of some Optimization Problems in Planning

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

    Sammanfattning : 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. LÄS MER