scientific article; zbMATH DE number 1499087

MaRDI QIDQ4501141zbMATH OpenFDO

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

Publication date 3 September 2000

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
• scientific article; zbMATH DE number 1424025
• 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:

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