Consensus string problem for multiple regular languages

DOI10.1007/978-3-319-53733-7_14MaRDI QIDQ5738997zbMATH OpenOpenAlexFDO

Authors Yo-Sub Han, Sang-Ki Ko, Timothy Ng, 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

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

Recommendations

• Consensus string problem for multiple regular languages
• Closest substring problems for regular languages
• Closest substring problems for regular languages
• The consensus string problem for a metric is NP-complete
• On the Efficiency of the Hamming C-Centerstring Problems

Cites work

• scientific article; zbMATH DE number 2081011 (Why is no real title available?)
• A Second Course in Formal Languages and Automata Theory
• A three-string approach to the closest string problem
• Additive distances and quasi-distances between words
• Approximately matching context-free languages
• Computing the edit distance of a regular language
• Descriptional and computational complexity of finite automata -- a survey
• Distances between languages and reflexivity of relations
• Efficient algorithms for consensus string problems minimizing both distance sum and radius
• Encyclopedia of Distances
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• How hard is computing the edit distance?
• Long packing and covering codes
• More efficient algorithms for closest string and substring problems
• On covering problems of codes
• On the covering radius of codes
• On the hardness of the consensus string problem
• Quasi-distances and weighted finite automata
• State complexity of neighbourhoods and approximate pattern matching
• The consensus string problem for a metric is NP-complete
• The edit-distance between a regular language and a context-free language
• The intractability of computing the Hamming distance

Cited in

(6)

• The most probable string: an algorithmic study
• Closest substring problems for regular languages
• Closest substring problems for regular languages
• The consensus string problem for a metric is NP-complete
• Consensus string problem for multiple regular languages
• Consensual Definition of Languages by Regular Sets

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5738997)