Consensus string problem for multiple regular languages

The consensus string (or centre string, closest string) of a set S of strings is defined as a string which is within a radius r from all strings in S. We study the consensus string problem for multiple languages recognized by finite automata (FAs). We define the consensus string of languages to be within distance at most r to some string in each of the languages. We also study the decidability and computational complexity of the consensus string problem for multiple formal language instances. We show that the consensus string problem for multiple regular languages is PSPACE -complete even when the radius r is fixed. We prove that the problem can be solved in polynomial time when the number of languages is fixed. Finally, we study that the consensus string problem for the class of input-driven languages and show that the problem is decidable.

Authors

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

Keywords

• Consensus string problem
• Computational complexity
• Regular languages
• Edit-distance