The parameterized complexity of some problems in logic and linguistics

DOI10.1007/3-540-58140-5_10MaRDI QIDQ4501141zbMATH OpenFDO

Authors Michael R. Fellows, Bruce M. Kapron, Michael T. Hallett, Rodney G. Downey, Todd Wareham

Publication date 3 September 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-58140-5_10

zbMATH Keywords

context-sensitive grammarfixed-parameter tractabilityintractabilityminimum axiom setparameterized computational complexityphonological derivationreachability in Petri netstractability

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Grammars and rewriting systems (68Q42) Linguistics (91F20)

Recommendations

• On the parameterized complexity of short computation and factorization
• scientific article; zbMATH DE number 6819785
• Descriptive and parameterized complexity
• Finding consistent categorial grammars of bounded value: a parameterized approach

Cited in

(21)

• Parameterized circuit complexity and the \(W\) hierarchy
• Threshold dominating sets and an improved characterization of \(W[2]\)
• Approximability of flow shop scheduling
• The parameterized complexity of sequence alignment and consensus
• On the parameterized complexity of short computation and factorization
• The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
• Perfect Code is \(W[1]\)-complete
• The Turing way to parameterized complexity
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• \(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling
• The complexity of irredundant sets parameterized by size
• Inferring local transition functions of discrete dynamical systems from observations of system behavior
• An algorithm for canonical forms of finite subsets of \(\mathbb {Z}^d\) up to affinities
• The birth and early years of parameterized complexity
• A basic parameterized complexity primer
• On the parameterised complexity of string morphism problems
• A Purely Democratic Characterization of W[1]
• On the difficulty of designing good classifiers
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• The complexity ecology of parameters: An illustration using bounded max leaf number
• Chordless paths through three vertices

This page was built for publication: The parameterized complexity of some problems in logic and linguistics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4501141)