2026-07-22T01:29:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6479 2024-03-06T10:38:23Z ddc:004 open_access

Piecewise Testable Languages and Nondeterministic Automata Masopust, Tomás automata logics languages k-piecewise testability nondeterminism 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tomás Masopust 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.67 urn:nbn:de:0030-drops-64799 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.67 eng https://creativecommons.org/licenses/by/3.0/legalcode