Efficient Separability of Regular Languages by Subsequences and Suffixes

Wojciech CzerwińskiWojciech Czerwiński, Wim MartensWim Martens, Tomáš MasopustTomáš Masopust

ISBN: 978-3-642-39211-5
DOI Link

Wojciech Czerwiński, Wim Martens, Tomáš Masopust
Efficient Separability of Regular Languages by Subsequences and Suffixes
Proc. of 40th International Colloquium on Automata, Languages, and Programming (ICALP), volume 7966 of LNCS, 150-161, 2013. Springer

Details
Bibtex

KurzfassungAbstract
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 variants thereof. We give characterizations of when two languages can be separated and present an overview of when these problems can be decided in polynomial time if K and L are given by nondeterministic automata.
Forschungsgruppe:Research Group: Information Systems„Information Systems“ befindet sich nicht in der Liste (Computational Logic, Automatentheorie, Wissensverarbeitung, Knowledge-Based Systems, Knowledge Systems, Wissensbasierte Systeme, Logische Programmierung und Argumentation, Algebra und Diskrete Strukturen, Knowledge-aware Artificial Intelligence, Algebraische und logische Grundlagen der Informatik) zulässiger Werte für das Attribut „Forschungsgruppe“.Knowledge-Based Systems

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-39212-2_16.

@inproceedings{CMM2013,
  author    = {Wojciech Czerwi{\'{n}}ski and Wim Martens and Tom{\'{a}}{\v{s}}
               Masopust},
  title     = {Efficient Separability of Regular Languages by Subsequences and
               Suffixes},
  booktitle = {Proc. of 40th International Colloquium on Automata, Languages,
               and Programming (ICALP)},
  series    = {LNCS},
  volume    = {7966},
  publisher = {Springer},
  year      = {2013},
  pages     = {150-161},
  doi       = {10.1007/978-3-642-39212-2_16}
}