Selected publications at LSV

The piecewise testable separability problem asks, given two input languages, whether there exists a piecewise testable language that contains the first input language and is disjoint from the second. We prove a general characterisation of piecewise testable separability on languages in a well-quasi-order, in terms of ideals of the ordering. This subsumes the known characterisations in the case of finite words. In the case of finite ranked trees ordered by homeomorphic embedding, we show using effective representations for tree ideals that it entails the decidability of piecewise testable separability when the input languages are regular. A final byproduct is a new proof of the decidability of whether an input regular language of ranked trees is piecewise testable, which was first shown in the unranked case by Bojańczyk, Segoufin, and Straubing (Log. Meth. in Comput. Sci., 8(3:26), 2012).

   address = {Rome, Italy},
   author = {Goubault{-}Larrecq, Jean and Schmitz, Sylvain},
   booktitle = {{P}roceedings of the 43rd {I}nternational {C}olloquium on {A}utomata, {L}anguages and {P}rogramming ({ICALP}'16)~-- {P}art~{II}},
   DOI = {10.4230/LIPIcs.ICALP.2016.97},
   editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
   month = jul,
   pages = {97:1-97:15},
   publisher = {Leibniz-Zentrum f{\"u}r Informatik},
   series = {Leibniz International Proceedings in Informatics},
   title = {Deciding Piecewise Testable Separability for Regular Tree Languages},
   url = {},
   volume = {55},
   year = {2016},

About LSV

Select by Year