Geodesic
A Characterization for Decidable Separability by Piecewise Testable Languages
Discrete mathematics & theoretical computer science, FCT '15, Tome 19 (2017-2018) no. 4.

Voir la notice de l'article provenant de la source Episciences

The separability problem for word languages of a class $\mathcal{C}$ by languages of a class $\mathcal{S}$ asks, for two given languages $I$ and $E$ from $\mathcal{C}$, whether there exists a language $S$ from $\mathcal{S}$ that includes $I$ and excludes $E$, that is, $I \subseteq S$ and $S\cap E = \emptyset$. In this work, we assume some mild closure properties for $\mathcal{C}$ and study for which such classes separability by a piecewise testable language (PTL) is decidable. We characterize these classes in terms of decidability of (two variants of) an unboundedness problem. From this, we deduce that separability by PTL is decidable for a number of language classes, such as the context-free languages and languages of labeled vector addition systems. Furthermore, it follows that separability by PTL is decidable if and only if one can compute for any language of the class its downward closure wrt. the scattered substring ordering (i.e., if the set of scattered substrings of any language of the class is effectively regular). The obtained decidability results contrast some undecidability results. In fact, for all (non-regular) language classes that we present as examples with decidable separability, it is undecidable whether a given language is a PTL itself. Our characterization involves a result of independent interest, which states that for any kind of languages $I$ and $E$, non-separability by PTL is equivalent to the existence of common patterns in $I$ and $E$. 
@article{DMTCS_2017_19_4_a2,
     author = {Czerwi\'nski, Wojciech and Martens, Wim and van Rooijen, Lorijn and Zeitoun, Marc and Zetzsche, Georg},
     title = {A {Characterization} for {Decidable} {Separability} by {Piecewise} {Testable} {Languages}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {19},
     number = {4},
     year = {2017-2018},
     doi = {10.23638/DMTCS-19-4-1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-4-1/}
}
TY  - JOUR
AU  - Czerwiński, Wojciech
AU  - Martens, Wim
AU  - van Rooijen, Lorijn
AU  - Zeitoun, Marc
AU  - Zetzsche, Georg
TI  - A Characterization for Decidable Separability by Piecewise Testable Languages
JO  - Discrete mathematics & theoretical computer science
PY  - 2017-2018
VL  - 19
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-4-1/
DO  - 10.23638/DMTCS-19-4-1
LA  - en
ID  - DMTCS_2017_19_4_a2
ER  - 
%0 Journal Article
%A Czerwiński, Wojciech
%A Martens, Wim
%A van Rooijen, Lorijn
%A Zeitoun, Marc
%A Zetzsche, Georg
%T A Characterization for Decidable Separability by Piecewise Testable Languages
%J Discrete mathematics & theoretical computer science
%D 2017-2018
%V 19
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-4-1/
%R 10.23638/DMTCS-19-4-1
%G en
%F DMTCS_2017_19_4_a2
Czerwiński, Wojciech; Martens, Wim; van Rooijen, Lorijn; Zeitoun, Marc; Zetzsche, Georg. A Characterization for Decidable Separability by Piecewise Testable Languages. Discrete mathematics & theoretical computer science, FCT '15, Tome 19 (2017-2018) no. 4. doi : 10.23638/DMTCS-19-4-1. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-4-1/

Cité par Sources :