Piecewise Testable Languages and Nondeterministic Automata

Kód výsledku v 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>

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

Piecewise Testable Languages and Nondeterministic Automata

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Piecewise Testable Languages and Nondeterministic Automata

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

Kód důvěrnosti údajů

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

Název statě ve sborníku

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

ISBN

978-3-95977-016-3

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

14

Strana od-do

—

Název nakladatele

Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik

Místo vydání

Dagstuhl

Místo konání akce

Krakow

Datum konání akce

22. 8. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—