On the Complexity of k-Piecewise Testability and the Depth of Automata

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

Toggle side column

On the Complexity of k-Piecewise Testability and the Depth of Automata

Tomáš MasopustTomáš Masopust,  Michaël ThomazoMichaël Thomazo
On the Complexity of k-Piecewise Testability and the Depth of Automata


Tomáš Masopust, Michaël Thomazo
On the Complexity of k-Piecewise Testability and the Depth of Automata
In I. Potapov, eds., Proc. 19th International Conference on Developments in Language Theory (DLT'15), volume 9168 of LNCS, 364-376, 2015. Springer
  • KurzfassungAbstract
    For a non-negative integer k, a language is k-piecewise testable (k-PT) if it is a finite boolean combination of languages of the form \Sigma^*a1\Sigma^*...\Sigma^*an for ai in \Sigma and 0 <= n <= k. We study the following problem: Given a DFA recognizing a piecewise testable language, decide whether the language is k-PT. We provide a complexity bound on this problem and a detailed analysis for small k's. The result can be use to find the minimal k for which the language is k-PT. We show that the upper bound on k given by the depth of the minimal DFA can be exponentially bigger than the minimal possible k, and provide a tight upper bound on the depth of the minimal DFA recognizing a k-PT language.
  • Projekt:Project: DIAMOND
  • Forschungsgruppe:Research Group: Wissensbasierte Systeme
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-21500-6_29.
@inproceedings{MT2015,
  author    = {Tom{\'{a}}{\v{s}} Masopust and Micha{\"{e}}l Thomazo},
  title     = {On the Complexity of k-Piecewise Testability and the Depth of
               Automata},
  editor    = {I. Potapov},
  booktitle = {Proc. 19th International Conference on Developments in Language
               Theory (DLT'15)},
  series    = {LNCS},
  volume    = {9168},
  publisher = {Springer},
  year      = {2015},
  pages     = {364-376},
  doi       = {10.1007/978-3-319-21500-6_29}
}