Consensus string problem for multiple regular languages

DOI10.1016/j.ic.2020.104615zbMath1497.68269OpenAlexW4210245256MaRDI QIDQ2042725

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

Publication date: 21 July 2021

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2020.104615

zbMATH Keywords

computational complexityregular languagesedit-distanceconsensus string problem

Mathematics Subject Classification ID

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

Related Items (1)

Special issue: Selected papers of the 11th international conference on language and automata theory and applications, LATA 2017

Uses Software

• PROSITE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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?
• State complexity of prefix distance
• Computing the edit distance of a regular language
• State Complexity of Neighbourhoods and Approximate Pattern Matching
• Marrying Words and Trees
• Visibly pushdown languages
• More Efficient Algorithms for Closest String and Substring Problems
• On the covering radius of codes
• Long packing and covering codes
• A linear-time algorithm for the 1-mismatch problem
• THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE
• Encyclopedia of Distances
• Input-driven pushdown automata for edit distance neighborhood
• Edit distance neighbourhoods of input-driven pushdown automata

This page was built for publication: Consensus string problem for multiple regular languages