Efficient Separability of Regular Languages by Subsequences and Suffixes

Wojciech Czerwiński, Wim Martens, Tomáš Masopust

When can two regular word languages K and L be separated by a simple language? We investigate this question and consider separation by piecewise- and suffix-testable languages and…