On k-piecewise testability (preliminary report)

Tomáš MasopustTomáš Masopust, Michaël ThomazoMichaël Thomazo

Download

Tomáš Masopust, Michaël Thomazo
On k-piecewise testability (preliminary report)
Technical Report, arXiv.org, volume CoRR abs/1412.1641, December 2014

Details
Bibtex

KurzfassungAbstract
A language is k-piecewise testable if it is a finite boolean combination of languages of the form Σ^∗a₁Σ^∗⋯Σ^∗a_nΣ^∗, where a_i∈Σ and 0≤n≤k. We investigate the problem, given a minimal DFA recognizing a piecewise testable language, what is the minimal k for which the language is k-piecewise testable? It was shown by Klíma and Polák that such a k is bounded by the depth of the minimal DFA. We first provide the complexity bound to decide whether a given minimal DFA represents a k-piecewise testable language for a fixed k, which then results in an algorithm that is single exponential with respect to the size of the DFA and double exponential with respect to the resulting k. We provide a detailed complexity analysis for k≤2. Finally, we generalize a result valid for DFAs to NFAs and show that the upper bound given by the depth of the minimal DFA can be exponentially far from the minimal k.
Weitere Informationen unter:Further Information: Link
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@techreport{MT2014,
  author      = {Tom{\'{a}}{\v{s}} Masopust and Micha{\"{e}}l Thomazo},
  title       = {On k-piecewise testability (preliminary report)},
  institution = {arXiv.org},
  year        = {2014},
  month       = {December}
}