Article3037: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Tomas Masopust (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorVorname=Tomáš |ErsterAutorNachname=Masopust |FurtherAuthors=Michaël Thomazo; }} {{Article |Referiert=1 |Title=On boo…“) |
Tomas Masopust (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
| Zeile 2: | Zeile 2: | ||
|ErsterAutorVorname=Tomáš | |ErsterAutorVorname=Tomáš | ||
|ErsterAutorNachname=Masopust | |ErsterAutorNachname=Masopust | ||
|FurtherAuthors=Michaël Thomazo; | |FurtherAuthors=Michaël Thomazo; | ||
}} | }} | ||
{{Article | {{Article | ||
| Zeile 13: | Zeile 13: | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=A regular language is k-piecewise testable (k -PT) if it is a Boolean combination of languages of the form L_{a_1a_2…a_n} = Σ*a_1Σ*a_2Σ*⋯Σ*a_nΣ*, where a_i ∈ Σ and 0≤n≤k. Given a finite automaton A, if the language L(A) is piecewise testable, we want to express it as a Boolean combination of languages of the above form. The idea is as follows. If the language is k-PT, then there exists a congruence ∼_k of finite index such that L(A) is a finite union of ∼_k-classes. Every such class is characterized by an intersection of languages of the from L_u, for the length of u at most k, and their complements. To represent the ∼_k-classes, we make use of the ∼_k-canonical DFA. We identify the states of the ∼_k-canonical DFA whose union forms the language L(A) and use them to construct the required Boolean combination. We study the computational and descriptional complexity of related problems. | |Abstract=A regular language is k-piecewise testable (k -PT) if it is a Boolean combination of languages of the form L_{a_1a_2…a_n} = Σ*a_1Σ*a_2Σ*⋯Σ*a_nΣ*, where a_i ∈ Σ and 0≤n≤k. Given a finite automaton A, if the language L(A) is piecewise testable, we want to express it as a Boolean combination of languages of the above form. The idea is as follows. If the language is k-PT, then there exists a congruence ∼_k of finite index such that L(A) is a finite union of ∼_k-classes. Every such class is characterized by an intersection of languages of the from L_u, for the length of u at most k, and their complements. To represent the ∼_k-classes, we make use of the ∼_k-canonical DFA. We identify the states of the ∼_k-canonical DFA whose union forms the language L(A) and use them to construct the required Boolean combination. We study the computational and descriptional complexity of related problems. | ||
|Download=Tcs bool.pdf | |||
|DOI Name=10.1016/j.tcs.2017.01.017 | |DOI Name=10.1016/j.tcs.2017.01.017 | ||
|Projekt=Cfaed, DIAMOND | |Projekt=Cfaed, DIAMOND | ||
|Forschungsgruppe=Wissensbasierte Systeme | |Forschungsgruppe=Wissensbasierte Systeme | ||
}} | }} | ||
Version vom 4. Mai 2017, 17:52 Uhr
On boolean combinations forming piecewise testable languages
Tomáš MasopustTomáš Masopust, Michaël ThomazoMichaël Thomazo
Tomáš Masopust, Michaël Thomazo
On boolean combinations forming piecewise testable languages
Theoretical Computer Science, to appear
On boolean combinations forming piecewise testable languages
Theoretical Computer Science, to appear
- KurzfassungAbstract
A regular language is k-piecewise testable (k -PT) if it is a Boolean combination of languages of the form L_{a_1a_2…a_n} = Σ*a_1Σ*a_2Σ*⋯Σ*a_nΣ*, where a_i ∈ Σ and 0≤n≤k. Given a finite automaton A, if the language L(A) is piecewise testable, we want to express it as a Boolean combination of languages of the above form. The idea is as follows. If the language is k-PT, then there exists a congruence ∼_k of finite index such that L(A) is a finite union of ∼_k-classes. Every such class is characterized by an intersection of languages of the from L_u, for the length of u at most k, and their complements. To represent the ∼_k-classes, we make use of the ∼_k-canonical DFA. We identify the states of the ∼_k-canonical DFA whose union forms the language L(A) and use them to construct the required Boolean combination. We study the computational and descriptional complexity of related problems. - Projekt:Project: Cfaed, DIAMOND
- Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems
@article{MT2017,
author = {Tom{\'{a}}{\v{s}} Masopust and Micha{\"{e}}l Thomazo},
title = {On boolean combinations forming piecewise testable languages},
journal = {Theoretical Computer Science},
year = {2017},
doi = {10.1016/j.tcs.2017.01.017}
}
