Piecewise Testable Languages and Nondeterministic Automata

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F16%3A00462039" target="_blank" >RIV/67985840:_____/16:00462039 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.67" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.67</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.67" target="_blank" >10.4230/LIPIcs.MFCS.2016.67</a>

Result language
angličtina
Original language name
Piecewise Testable Languages and Nondeterministic Automata
Original language description
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_iinSigma$ and $0le n le k$. Given a DFA $A$ and $kge 0$, it is an NL-complete problem to decide whether the language $L(A)$ is piecewise testable and, for $kge 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.
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
ISBN
978-3-95977-016-3
ISSN
1868-8969
e-ISSN
—
Number of pages
14
Pages from-to
—
Publisher name
Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik
Place of publication
Dagstuhl
Event location
Krakow
Event date
Aug 22, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)