On the Complexity of k-Piecewise Testability and the Depth of Automata
Aus International Center for Computational Logic
On the Complexity of k-Piecewise Testability and the Depth of Automata
Vortrag von Tomáš Masopust
- Veranstaltungsort: APB 3105
- Beginn: 31. August 2015 um 14:50
- Ende: 31. August 2015 um 15:50
- Event series: KBS Seminar
- iCal
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.
