Document Open Access Logo

Piecewise Testable Languages and Nondeterministic Automata

Author Tomás Masopust

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.67.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Tomás Masopust

Cite As Get BibTex

Tomás Masopust. Piecewise Testable Languages and Nondeterministic Automata. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.67

Abstract

A regular language is k-piecewise testable if it is a finite boolean combination of languages of the form Sigma^* a_1 Sigma^* ... Sigma^* a_n Sigma^*, where a_i in Sigma and 0 <= n <= k. Given a DFA A and k >= 0, it is an NL-complete problem to decide whether the language L(A) is piecewise testable and, for k >= 4, it is coNP-complete to decide whether the language L(A) is k-piecewise testable. It is known that the depth of the minimal DFA serves as an upper bound on k. Namely, if L(A) is piecewise testable, then it is k-piecewise testable for k equal to the depth of A. In this paper, we show that some form of nondeterminism does not violate this upper bound result. Specifically, we define a class of NFAs, called ptNFAs, that recognize piecewise testable languages and show that the depth of a ptNFA provides an (up to exponentially better) upper bound on k than the minimal DFA. We provide an application of our result, discuss the relationship between k-piecewise testability and the depth of NFAs, and study the complexity of k-piecewise testability for ptNFAs.

Subject Classification

Keywords
  • automata
  • logics
  • languages
  • k-piecewise testability
  • nondeterminism

Metrics

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

References

  1. A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. Google Scholar
  2. J. Almeida, J. C. Costa, and M. Zeitoun. Pointlike sets with respect to R and J. Journal of Pure and Applied Algebra, 212(3):486-499, 2008. Google Scholar
  3. J. Almeida and M. Zeitoun. The pseudovariety J is hyperdecidable. RAIRO - Theoretical Informatics and Applications, 31(5):457-482, 1997. Google Scholar
  4. M. Bojanczyk, L. Segoufin, and H. Straubing. Piecewise testable tree languages. Logical Methods in Computer Science, 8(3), 2012. Google Scholar
  5. J. A. Brzozowski and F. E. Fich. Languages of R-trivial monoids. Journal of Computer and System Sciences, 20(1):32-49, 1980. Google Scholar
  6. S. Cho and D. T. Huynh. Finite-automaton aperiodicity is PSPACE-complete. Theoretical Computer Science, 88(1):99-116, 1991. Google Scholar
  7. R. S. Cohen and J. A. Brzozowski. Dot-depth of star-free events. Journal of Computer and System Sciences, 5(1):1-16, 1971. Google Scholar
  8. W. Czerwiński, W. Martens, and T. Masopust. Efficient separability of regular languages by subsequences and suffixes. In International Colloquium on Automata, Languages and Programming (ICALP), volume 7966 of LNCS, pages 150-161, 2013. Google Scholar
  9. W. Czerwiński, W. Martens, L. van Rooijen, and M. Zeitoun. A note on decidable separability by piecewise testable languages. In Fundamentals of Computation Theory (FCT), volume 9210 of LNCS, pages 173-185, 2015. Google Scholar
  10. V. Diekert, P. Gastin, and M. Kufleitner. A survey on small fragments of first-order logic over finite words. International Journal of Foundations of Computer Science, 19(3):513-548, 2008. Google Scholar
  11. J. Fu, J. Heinz, and H. G. Tanner. An algebraic characterization of strictly piecewise languages. In Theory and Applications of Models of Computation (TAMC), volume 6648 of LNCS, pages 252-263, 2011. Google Scholar
  12. P. García and J. Ruiz. Learning k-testable and k-piecewise testable languages from positive data. Grammars, 7:125-140, 2004. Google Scholar
  13. P. García and E. Vidal. Inference of k-testable languages in the strict sense and application to syntactic pattern recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(9):920-925, 1990. Google Scholar
  14. P. Hofman and W. Martens. Separability by short subsequences and subwords. In International Conference on Database Theory (ICDT), volume 31 of LIPIcs, pages 230-246, 2015. Google Scholar
  15. Š. Holub, G. Jirásková, and T. Masopust. On upper and lower bounds on the length of alternating towers. In Mathematical Foundations of Computer Science (MFCS), volume 8634 of LNCS, pages 315-326, 2014. Google Scholar
  16. Š. Holub, T. Masopust, and M. Thomazo. Alternating towers and piecewise testable separators. CoRR, 2014. Submitted. URL: http://arxiv.org/abs/1409.3943.
  17. H. B. Hunt III. On the Time and Tape Complexity of Languages. PhD thesis, Department of Computer Science, Cornell University, Ithaca, NY, 1973. Google Scholar
  18. 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
  19. O. Klíma, M. Kunc, and L. Polák. Deciding k-piecewise testability. Submitted. Google Scholar
  20. O. Klíma and L. Polák. Alternative automata characterization of piecewise testable languages. In Developments in Language Theory (DLT), volume 7907 of LNCS, pages 289-300, 2013. Google Scholar
  21. L. Kontorovich, C. Cortes, and M. Mohri. Kernel methods for learning languages. Theoretical Computer Science, 405(3):223-236, 2008. Google Scholar
  22. M. Krötzsch, T. Masopust, and M. Thomazo. On the complexity of university for partially ordered NFAs. In Mathematical Foundations of Computer Science (MFCS), volume 58 of LIPIcs, pages 62:1-62:14, 2016. Google Scholar
  23. M. Kufleitner and A. Lauser. Around dot-depth one. International Journal of Foundations of Computer Science, 23(6):1323-1340, 2012. Google Scholar
  24. W. Martens, F. Neven, M. Niewerth, and T. Schwentick. Bonxai: Combining the simplicity of DTD with the expressiveness of XML schema. In Principles of Database Systems (PODS), pages 145-156. ACM, 2015. Google Scholar
  25. T. Masopust and M. Thomazo. On the complexity of k-piecewise testability and the depth of automata. In Developments in Language Theory (DLT), volume 9168 of LNCS, pages 364-376, 2015. Google Scholar
  26. J. Myhill. Finite automata and representation of events. Technical report, Wright Air Development Center, 1957. Google Scholar
  27. D. Perrin and J.-E. Pin. First-order logic and star-free sets. Journal of Computer and System Sciences, 32(3):393-406, 1986. Google Scholar
  28. D. Perrin and J.-E. Pin. Infinite words: Automata, semigroups, logic and games, volume 141 of Pure and Applied Mathematics. Elsevier, 2004. Google Scholar
  29. T. Place, L. van Rooijen, and M. Zeitoun. Separating regular languages by piecewise testable and unambiguous languages. In Mathematical Foundations of Computer Science (MFCS), volume 8087 of LNCS, pages 729-740, 2013. Google Scholar
  30. J. Rogers, J. Heinz, G. Bailey, M. Edlefsen, M. Visscher, D. Wellcome, and S. Wibel. On languages piecewise testable in the strict sense. In Mathematics of Language (MOL), volume 6149 of LNAI, pages 255-265, 2010. Google Scholar
  31. J. Rogers, J. Heinz, M. Fero, J. Hurst, D. Lambert, and S. Wibel. Cognitive and sub-regular complexity. In Formal Grammar (FG), volume 8036 of LNCS, pages 90-108, 2013. Google Scholar
  32. T. Schwentick, D. Thérien, and H. Vollmer. Partially-ordered two-way automata: A new characterization of DA. In Developments in Language Theory (DLT), volume 2295 of LNCS, pages 239-250, 2001. Google Scholar
  33. I. Simon. Hierarchies of Events with Dot-Depth One. PhD thesis, Department of Applied Analysis and Computer Science, University of Waterloo, Canada, 1972. Google Scholar
  34. J. Stern. Complexity of some problems from the theory of automata. Information and Control, 66(3):163-176, 1985. Google Scholar
  35. L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time: Preliminary report. In Symposium on the Theory of Computing (STOC), pages 1-9. ACM, 1973. Google Scholar
  36. W. Thomas. Classifying regular events in symbolic logic. Journal of Computer and System Sciences, 25(3):360-376, 1982. Google Scholar
  37. A. N. Trahtman. Piecewise and local threshold testability of DFA. In Fundamentals of Computation Theory (FCT), volume 2138 of LNCS, pages 347-358, 2001. Google Scholar
  38. L. van Rooijen. A combinatorial approach to the separation problem for regular languages. PhD thesis, LaBRI, University of Bordeaux, France, 2014. 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