Semantisches Browsen

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche
Techreport3008
Abstract A language is <i>k</i>-piecewi
A language is <i>k</i>-piecewise testable if it is a finite boolean combination of languages of the form Σ<sup>∗</sup>a<sub>1</sub>Σ<sup>∗</sup>⋯Σ<sup>∗</sup>a<sub>n</sub>Σ<sup>∗</sup>, where a<sub>i</sub>∈Σ and 0≤n≤k. We investigate the problem, given a minimal DFA recognizing a piecewise testable language, what is the minimal <i>k</i> for which the language is <i>k</i>-piecewise testable? It was shown by Klíma and Polák that such a <i>k</i> is bounded by the depth of the minimal DFA. We first provide the complexity bound to decide whether a given minimal DFA represents a <i>k</i>-piecewise testable language for a fixed <i>k</i>, 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 <i>k</i>. We provide a detailed complexity analysis for <i>k</i>≤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 <i>k</i>.
far from the minimal <i>k</i>.  +
Archivierungsnummer CoRR abs/1412.1641  +
Author Tomáš Masopust + , Michaël Thomazo +
BibTex
@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}
}
Bibtype Techreport  +
Download On k-pt (report) 2.pdf  +
ErsterAutorNachname Masopust  +
ErsterAutorVorname Tomáš  +
Forschungsgruppe Wissensbasierte Systeme +
Institution arXiv.org  +
Link http://arxiv.org/abs/1412.1641  +
Month Dezember  +
Publication text Tomáš Masopust, Michaël Thomazo<br />
Tomáš Masopust, Michaël Thomazo<br /> '''[[Techreport3008|On k-piecewise testability (preliminary report)]]''' <br />__NOTOC__Technical Report, ''arXiv.org'', volume CoRR abs/1412.1641, December 2014<br/><span class="glyphicon glyphicon-chevron-right" style="font-size: 85%;" ></span> [[Techreport3008|Details]] <span class="glyphicon glyphicon-chevron-right" style="font-size: 85%; margin-left: 2ex; "></span> [[Media:On k-pt (report) 2.pdf|Download]]
[[Media:On k-pt (report) 2.pdf|Download]]  +
Publication text en Tomáš Masopust, Michaël Thomazo<br />
Tomáš Masopust, Michaël Thomazo<br /> '''[[Techreport3008/en|On k-piecewise testability (preliminary report)]]''' <br />__NOTOC__Technical Report, ''arXiv.org'', volume CoRR abs/1412.1641, December 2014<br/><span class="glyphicon glyphicon-chevron-right" style="font-size: 85%;" ></span> [[Techreport3008|Details]] <span class="glyphicon glyphicon-chevron-right" style="font-size: 85%; margin-left: 2ex;" ></span> [[Media:On k-pt (report) 2.pdf|Download]]
[[Media:On k-pt (report) 2.pdf|Download]]  +
Title On k-piecewise testability (preliminary report)  +
Type techreport  +
Year 2014  +
Hat Abfrage
Dieses Attribut ist ein Spezialattribut in diesem Wiki.
Techreport3008 + , Techreport3008 + , Techreport3008 + , Techreport3008 + , Techreport3008 + , Techreport3008 +
Kategorien Techreport , Publikation
Zuletzt geändert
Dieses Attribut ist ein Spezialattribut in diesem Wiki.
24 Mai 2016 16:02:44  +
verstecke Attribute die hierhin verlinken 
Techreport3008/en + Weiterleitungsseite
 

 

Bitte den Namen einer Seite angeben, um mit dem Browsen zu beginnen.