Consensus String Problem for Multiple Regular Languages

DOI10.1007/978-3-319-53733-7_14zbMath1485.68143OpenAlexW2589071047MaRDI QIDQ5738997

Timothy Ng, Sang-Ki Ko, Yo-Sub Han, Kai Salomaa

Publication date: 1 June 2017

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-53733-7_14

zbMATH Keywords

computational complexityregular languagesedit-distanceconsensus string problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Formal languages and automata (68Q45) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

Closest substring problems for regular languages

Cites Work

• Unnamed Item
• Unnamed Item
• On the hardness of the consensus string problem
• A three-string approach to the closest string problem
• Descriptional and computational complexity of finite automata -- a survey
• The intractability of computing the Hamming distance
• Approximately matching context-free languages
• On covering problems of codes
• Efficient algorithms for consensus string problems minimizing both distance sum and radius
• The consensus string problem for a metric is NP-complete
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Distances between languages and reflexivity of relations
• How hard is computing the edit distance?
• Computing the edit distance of a regular language
• State Complexity of Neighbourhoods and Approximate Pattern Matching
• A Second Course in Formal Languages and Automata Theory
• More Efficient Algorithms for Closest String and Substring Problems
• On the covering radius of codes
• Long packing and covering codes
• THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE
• Quasi-Distances and Weighted Finite Automata
• Encyclopedia of Distances

This page was built for publication: Consensus String Problem for Multiple Regular Languages