Article3037: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Tomas Masopust (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Tomas Masopust (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
| Zeile 7: | Zeile 7: | ||
|Referiert=1 | |Referiert=1 | ||
|Title=On boolean combinations forming piecewise testable languages | |Title=On boolean combinations forming piecewise testable languages | ||
|To appear= | |To appear=0 | ||
|Year=2017 | |Year=2017 | ||
|Month=Juni | |||
|Journal=Theoretical Computer Science | |Journal=Theoretical Computer Science | ||
|Volume=682 | |||
|Pages=165-179 | |||
|Publisher=Elsevier | |||
}} | }} | ||
{{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. | ||
|ISSN=0304-3975 | |||
|Download=Tcs bool.pdf | |Download=Tcs bool.pdf | ||
|DOI Name=10.1016/j.tcs.2017.01.017 | |DOI Name=10.1016/j.tcs.2017.01.017 | ||
Aktuelle Version vom 11. Juni 2017, 20:00 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, 682:165-179, June 2017
On boolean combinations forming piecewise testable languages
Theoretical Computer Science, 682:165-179, June 2017
- 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},
volume = {682},
publisher = {Elsevier},
year = {2017},
month = {June},
pages = {165-179},
doi = {10.1016/j.tcs.2017.01.017}
}
