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

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)

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

(20)

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

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)