scientific article; zbMATH DE number 1775632

MaRDI QIDQ4544433zbMATH OpenFDO

Authors H. Todd Wareham

Publication date 4 August 2002

zbMATH Keywords

non-polynomial time algorithmic behaviors

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Recommendations

• The parameterized complexity of chosen problems for finite automata on trees
• A multi-parameter analysis of hard problems on deterministic finite automata
• The complexity of intersecting finite automata having few final states
• On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
• Minimizing finite automata is computationally hard

Cited in

(21)

• On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
• Problems on finite automata and the exponential time hypothesis
• The Turing way to parameterized complexity
• The complexity of compressed membership problems for finite automata
• A multi-parameter analysis of hard problems on deterministic finite automata
• A parametric analysis of the state-explosion problem in model checking
• Problems on finite automata and the exponential time hypothesis
• Parameterized complexity of basic decision problems for tree automata
• The parameterized complexity of chosen problems for finite automata on trees
• The complexity of intersecting finite automata having few final states
• Fixed Structure Complexity
• Parameterized Complexity and Approximability of the SLCS Problem
• Parameterized complexity and approximability of the longest compatible sequence problem
• Synchronizing series-parallel deterministic finite automata with loops and related problems
• On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
• Synchronizing words and monoid factorization, yielding a new parameterized complexity class?
• On the Complexity of Bounded Context Switching.
• Fine-grained complexity of safety verification
• Algorithms for checking intersection non-emptiness of regular expressions
• Subset mapping problems in solvable automata
• Incremental algorithms for solving regular expression intersection non-emptiness

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 Q4544433)