Browse wiki
From International Center for Computational Logic
A regular language is k-piecewise testable … 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.criptional complexity of related problems. +
@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}
}
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}
}
Masopust +
Tomáš +
Tomáš Masopust, Michaël Thomazo<br/> … Tomáš Masopust, Michaël Thomazo<br/> '''[[Article3037|On boolean combinations forming piecewise testable languages]]''' <br/>__NOTOC__Theoretical Computer Science, 682:165-179, June 2017<br/><span class="fas fa-chevron-right" style="font-size: 85%;" ></span> [[Article3037|Details]] <span class="fas fa-chevron-right" style="font-size: 85%; margin-left: 2ex; "></span> [[Media:Tcs bool.pdf|Download]]:Tcs bool.pdf|Download]] +
Tomáš Masopust, Michaël Thomazo<br/> … Tomáš Masopust, Michaël Thomazo<br/> '''[[Article3037/en|On boolean combinations forming piecewise testable languages]]''' <br/>__NOTOC__Theoretical Computer Science, 682:165-179, June 2017<br/><span class="fas fa-chevron-right" style="font-size: 85%;" ></span> [[Article3037|Details]] <span class="fas fa-chevron-right" style="font-size: 85%; margin-left: 2ex;" ></span> [[Media:Tcs bool.pdf|Download]]:Tcs bool.pdf|Download]] +
Anzeigetitel„Anzeigetitel <span style="font-size:small;">(Display title of)</span>“ ist ein softwareseitig fest definiertes Attribut, das einen eindeutigen Anzeigetitel zu einem Objekt speichert und ihm zuweist. Es wird von <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a> zur Verfügung gestellt.
On boolean combinations forming piecewise testable languages +
Zuletzt geändert„Zuletzt geändert <span style="font-size:small;">(Modification date)</span>“ ist ein softwareseitig fest definiertes Attribut, das das Datum der letzten Änderung einer Seite speichert. Es wird von <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a> zur Verfügung gestellt.
11. Juni 2017, 18:00:02 +
Hat Abfrage„Hat Abfrage <span style="font-size:small;">(Has query)</span>“ ist ein softwareseitig fest definiertes Attribut, das die Metainformationen einer Abfrage als <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Subobject">Subobjekt</a> speichert. Es wird von <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a> zur Verfügung gestellt.
On boolean combinations forming piecewise testable languages +, On boolean combinations forming piecewise testable languages +, On boolean combinations forming piecewise testable languages +, On boolean combinations forming piecewise testable languages +, On boolean combinations forming piecewise testable languages + und On boolean combinations forming piecewise testable languages +
