Piecewise Testable Languages and Nondeterministic Automata

Tomáš MasopustTomáš Masopust

ISBN: 978-3-95977-016-3
ISSN: 1868-8969
Download
DOI Link

Tomáš Masopust
Piecewise Testable Languages and Nondeterministic Automata
In Piotr Faliszewski, Anca Muscholl, Rolf Niedermeier, eds., Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), volume 58 of Leibniz International Proceedings in Informatics, 67:1--67:14, 2016. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

Details
Bibtex

KurzfassungAbstract
A regular language is $k$-piecewise testable if it is a finite boolean combination of languages of the form $\Sigma^* a_1 \Sigma^* \cdots \Sigma^* a_n \Sigma^*$, where $a_i\in\Sigma$ and $0\le n \le k$. Given a DFA $A$ and $k\ge 0$, it is an NL-complete problem to decide whether the language $L(A)$ is piecewise testable and, for $k\ge 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.
Weitere Informationen unter:Further Information: Link
Projekt:Project: DIAMOND
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@inproceedings{M2016,
  author    = {Tom{\'{a}}{\v{s}} Masopust},
  title     = {Piecewise Testable Languages and Nondeterministic Automata},
  editor    = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  booktitle = {Proceedings of the 41st International Symposium on Mathematical
               Foundations of Computer Science (MFCS 2016)},
  series    = {Leibniz International Proceedings in Informatics},
  volume    = {58},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016},
  pages     = {67:1--67:14},
  doi       = {10.4230/LIPIcs.MFCS.2016.67}
}