Consensus string problem for multiple regular languages
type: Item
instance of: scholarly article
title: Consensus string problem for multiple regular languages
zbMATH Open document ID: 1497.68269
author: Yo-Sub Han
author: Sang-Ki Ko
author: Timothy Ng
author: Kai Salomaa
published in: Information and Computation
publication date: 2021-07-21T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7373415
zbMATH Keywords: consensus string problem
zbMATH Keywords: computational complexity
zbMATH Keywords: regular languages
zbMATH Keywords: edit-distance
describes a project that uses: PROSITE
MaRDI profile type: Publication
full work available at URL: j.ic.2020.104615
OpenAlex ID: W4210245256
cites work: Q3084798
cites work: Marrying Words and Trees
cites work: Visibly pushdown languages
cites work: Efficient algorithms for consensus string problems minimizing both distance sum and radius
cites work: On the hardness of the consensus string problem
cites work: Q5422230
cites work: Distances between languages and reflexivity of relations
cites work: Long packing and covering codes
cites work: Encyclopedia of Distances
cites work: On covering problems of codes
cites work: Input-driven pushdown automata for edit distance neighborhood
cites work: On the covering radius of codes
cites work: Q4474112
cites work: Fixed-parameter algorithms for CLOSEST STRING and related problems
cites work: THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE
cites work: Descriptional and computational complexity of finite automata -- a survey
cites work: Q3862379
cites work: Computing the edit distance of a regular language
cites work: Q5528329
cites work: More Efficient Algorithms for Closest String and Substring Problems
cites work: The intractability of computing the Hamming distance
cites work: Q3890112
cites work: Approximately matching context-free languages
cites work: State Complexity of Neighbourhoods and Approximate Pattern Matching
cites work: State complexity of prefix distance
cites work: Edit distance neighbourhoods of input-driven pushdown automata
cites work: A three-string approach to the closest string problem
cites work: Q4526776
cites work: How hard is computing the edit distance?
cites work: The consensus string problem for a metric is NP-complete
cites work: A linear-time algorithm for the 1-mismatch problem
DOI: 10.1016/J.IC.2020.104615
description: scientific article; zbMATH DE number 7373415