On k-piecewise testability (preliminary report)

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

On k-piecewise testability (preliminary report)

Tomáš MasopustTomáš Masopust,  Michaël ThomazoMichaël Thomazo
Tomáš Masopust, Michaël Thomazo
On k-piecewise testability (preliminary report)
Technical Report, arXiv.org, volume CoRR abs/1412.1641, December 2014
  • KurzfassungAbstract
    A language is k-piecewise testable if it is a finite boolean combination of languages of the form Σa1Σ⋯ΣanΣ, where ai∈Σ 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}
}