The \(k\)-distinct language: parameterized automata constructions

DOI10.1016/j.tcs.2016.01.029zbMath1335.68114OpenAlexW2252416325MaRDI QIDQ5964071

Ran Ben-Basat, Meirav Zehavi, Ariel Gabizon

Publication date: 26 February 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.01.029

zbMATH Keywords

automata theory\(k\)-path\(r\)-dimensional \(k\)-matchingparameterized complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) General topics in the theory of algorithms (68W01)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Improved deterministic algorithms for weighted matching and packing problems
• Algorithm engineering for color-coding with applications to signaling pathway detection
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• A faster parameterized algorithm for set packing
• Using nondeterminism to design efficient deterministic algorithms
• Narrow sieves for parameterized paths and packings
• Families of \(k\)-independent sets
• Parameterized Algorithms for Module Motif
• Some Results on more Flexible Versions of Graph Motif
• Representative Sets of Product Families
• Representative Families: A Unified Tradeoff-Based Approach
• The $$k$$-Distinct Language: Parameterized Automata Constructions
• Iterative Expansion and Color Coding
• Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets
• Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
• An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
• Improved Parameterized Algorithms for Weighted 3-Set Packing
• Faster Algebraic Algorithms for Path and Packing Problems
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• A Randomized Approximation Algorithm for Parameterized 3-D Matching Counting Problem
• Compact Normal Form for Regular Languages as Xor Automata
• Limits and Applications of Group Algebras for Parameterized Problems
• Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
• Balanced Hashing, Color Coding and Approximate Counting
• Vector sets for exhaustive testing of logic circuits
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• On Linear Time Minor Tests with Depth-First Search
• Color-coding
• The Parameterized Complexity of Counting Problems
• Finding Regular Simple Paths in Graph Databases
• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY

This page was built for publication: The \(k\)-distinct language: parameterized automata constructions