License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.62
URN: urn:nbn:de:0030-drops-96445
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9644/
Go to the corresponding LIPIcs Volume Portal

Fleischer, Lukas ; Kufleitner, Manfred

Testing Simon's congruence

pdf-format:
LIPIcs-MFCS-2018-62.pdf (0.4 MB)

Abstract

Piecewise testable languages are a subclass of the regular languages. There are many equivalent ways of defining them; Simon's congruence ~_k is one of the most classical approaches. Two words are ~_k-equivalent if they have the same set of (scattered) subwords of length at most k. A language L is piecewise testable if there exists some k such that L is a union of ~_k-classes.
For each equivalence class of ~_k, one can define a canonical representative in shortlex normal form, that is, the minimal word with respect to the lexicographic order among the shortest words in ~_k. We present an algorithm for computing the canonical representative of the ~_k-class of a given word w in A^* of length n. The running time of our algorithm is in O(|A| n) even if k <= n is part of the input. This is surprising since the number of possible subwords grows exponentially in k. The case k>n is not interesting since then, the equivalence class of w is a singleton. If the alphabet is fixed, the running time of our algorithm is linear in the size of the input word. Moreover, for fixed alphabet, we show that the computation of shortlex normal forms for ~_k is possible in deterministic logarithmic space.
One of the consequences of our algorithm is that one can check with the same complexity whether two words are ~_k-equivalent (with k being part of the input).

BibTeX - Entry

@InProceedings{fleischer_et_al:LIPIcs:2018:9644,
  author =	{Lukas Fleischer and Manfred Kufleitner},
  title =	{{Testing Simon's congruence}},
  booktitle =	{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)},
  pages =	{62:1--62:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9644},
  URN =		{urn:nbn:de:0030-drops-96445},
  doi =		{10.4230/LIPIcs.MFCS.2018.62},
  annote =	{Keywords: regular language, scattered subword, piecewise testability, string algorithm}
}

Keywords: regular language, scattered subword, piecewise testability, string algorithm
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI