On boolean combinations forming piecewise testable languages

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column

On boolean combinations forming piecewise testable languages

Tomáš MasopustTomáš Masopust,  Michaël ThomazoMichaël Thomazo
On boolean combinations forming piecewise testable languages


Tomáš Masopust, Michaël Thomazo
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: CfaedDIAMOND
  • 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}
}