Consensus string problem for multiple regular languages

DOI10.1016/J.IC.2020.104615zbMATH Open1497.68269OpenAlexW4210245256MaRDI QIDQ2042725FDOQ2042725

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

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Distances between languages and reflexivity of relations
• Computing the edit distance of a regular language
• Visibly pushdown languages
• More Efficient Algorithms for Closest String and Substring Problems
• A three-string approach to the closest string problem
• A linear-time algorithm for the 1-mismatch problem
• THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE
• Approximately matching context-free languages
• On covering problems of codes
• Encyclopedia of Distances
• Descriptional and computational complexity of finite automata -- a survey
• On the hardness of the consensus string problem
• Marrying Words and Trees
• How hard is computing the edit distance?
• The intractability of computing the Hamming distance
• On the covering radius of codes
• Efficient algorithms for consensus string problems minimizing both distance sum and radius
• The consensus string problem for a metric is NP-complete
• Long packing and covering codes
• State complexity of prefix distance
• State Complexity of Neighbourhoods and Approximate Pattern Matching
• Input-driven pushdown automata for edit distance neighborhood
• Edit distance neighbourhoods of input-driven pushdown automata

Cited In (1)

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

Uses Software

• PROSITE

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