scientific article; zbMATH DE number 1499087

zbMATH Open0946.03046MaRDI QIDQ4501141FDOQ4501141

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

Publication date: 3 September 2000

Title of this publication is not available (Why is that?)

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

zbMATH Keywords

fixed-parameter tractabilitytractabilityintractabilitycontext-sensitive grammarparameterized computational complexityreachability in Petri netsminimum axiom setphonological derivation

Mathematics Subject Classification ID

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

Cited In (21)

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

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)