Document Open Access Logo

Testing Simon's congruence

Authors Lukas Fleischer, Manfred Kufleitner

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.62.pdf
  • Filesize: 423 kB
  • 13 pages

Document Identifiers

Author Details

Lukas Fleischer
  • FMI, University of Stuttgart, Universitätsstraße 38, 70569 Stuttgart, Germany
Manfred Kufleitner
  • Department of Computer Science, Loughborough University, Epinal Way, Loughborough LE11 3TU, United Kingdom

Funding

  • Fleischer, Lukas: Supported by the German Research Foundation (DFG) under grant DI 435/5 - 2.

Cite As Get BibTex

Lukas Fleischer and Manfred Kufleitner. Testing Simon's congruence. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 62:1-62:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.62

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

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics on words
  • Theory of computation → Formal languages and automata theory
Keywords
  • regular language
  • scattered subword
  • piecewise testability
  • string algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sung Cho and Dung T. Huynh. Finite automaton aperiodicity is PSPACE-complete. Theoretical Computer Science, 88:96-116, 1991. Google Scholar
  2. Jie Fu, Jeffrey Heinz, and Herbert G. Tanner. An algebraic characterization of strictly piecewise languages. In Mitsunori Ogihara and Jun Tarui, editors, Theory and Applications of Models of Computation, volume 6648 of LNCS, pages 252-263, Berlin, Heidelberg, 2011. Springer. Google Scholar
  3. Graham Higman. Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society. Third Series, 2:326-336, 1952. Google Scholar
  4. Stepan Holub, Tomás Masopust, and Michaël Thomazo. Alternating towers and piecewise testable separators. CoRR, abs/1409.3943, 2014. Google Scholar
  5. J. E. Hopcroft and R. Karp. A linear algorithm for testing equivalence of finite automata. Technical Report 71-114, Dept. of Computer Science, Cornell U, December 1971. Google Scholar
  6. P. Karandikar, M. Kufleitner, and Ph. Schnoebelen. On the index of Simon’s congruence for piecewise testability. Information Processing Letters, 115(4):515-519, 2015. Google Scholar
  7. Kamilla Kátai-Urbán, Péter Pál Pach, Gabriella Pluhár, András Pongrácz, and Csaba Szabó. On the word problem for syntactic monoids of piecewise testable languages. In Semigroup Forum, volume 84, pages 323-332. Springer, 2012. Google Scholar
  8. O. Klíma, M. Kunc, and L. Polák. Deciding k-piecewise testability, submitted. Google Scholar
  9. Ondřej Klíma and Libor Polák. Alternative automata characterization of piecewise testable languages. In Marie-Pierre Béal and Olivier Carton, editors, DLT 2013, Proceedings, volume 7907 of Lecture Notes in Computer Science, pages 289-300. Springer, 2013. Google Scholar
  10. Leonid Aryeh Kontorovich, Corinna Cortes, and Mehryar Mohri. Kernel methods for learning languages. Theoretical Computer Science, 405(3):223-236, 2008. Google Scholar
  11. Tomás Masopust and Michaël Thomazo. On the complexity of k-piecewise testability and the depth of automata. In DLT 2015, Proceedings, volume 9168 of Lecture Notes in Computer Science, pages 364-376. Springer, 2015. Google Scholar
  12. Péter Pál Pach. Solving equations under Simon’s congruence. In JHSDM 2015, Proceedings, pages 201-206, 2015. Google Scholar
  13. Péter Pál Pach. Normal forms under Simon’s congruence. Semigroup Forum, Dec 2017. Google Scholar
  14. James Rogers, Jeffrey Heinz, Gil Bailey, Matt Edlefsen, Molly Visscher, David Wellcome, and Sean Wibel. On languages piecewise testable in the strict sense. In Christian Ebert, Gerhard Jäger, and Jens Michaelis, editors, The Mathematics of Language, pages 255-265, Berlin, Heidelberg, 2010. Springer. Google Scholar
  15. José Ruiz and Pedro García. Learning k-piecewise testable languages from positive data. In Laurent Miclet and Colin de la Higuera, editors, Grammatical Interference: Learning Syntax from Sentences, pages 203-210, Berlin, Heidelberg, 1996. Springer. Google Scholar
  16. Thomas Schwentick, Denis Thérien, and Heribert Vollmer. Partially-ordered two-way automata: A new characterization of DA. In DLT 2001, Proceedings, volume 2295 of LNCS, pages 239-250. Springer, 2002. Google Scholar
  17. Imre Simon. Hierarchies of events with dot-depth one. PhD thesis, University of Waterloo, 1972. Google Scholar
  18. Imre Simon. Piecewise testable events. In Autom. Theor. Form. Lang., 2nd GI Conf., volume 33 of LNCS, pages 214-222. Springer, 1975. Google Scholar
  19. Jacques Stern. Characterization of some classes of regular events. Theor. Comput. Sci., 35:17-42, 1985. Google Scholar
  20. Wolfgang Thomas. Classifying regular events in symbolic logic. J. Comput. Syst. Sci., 25:360-376, 1982. Google Scholar
  21. A. N. Trahtman. Piecewise and local threshold testability of DFA. In Rusins Freivalds, editor, FCT 2001, Proceedings, volume 2138 of LNCS, pages 347-358. Springer, 2001. Google Scholar
  22. Philipp Weis and Neil Immerman. Structure theorem and strict alternation hierarchy for FO² on words. Log. Methods Comput. Sci., 5(3):1-23, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact