2013 | OriginalPaper | Buchkapitel
Efficient Separability of Regular Languages by Subsequences and Suffixes
verfasst von : Wojciech Czerwiński, Wim Martens, Tomáš Masopust
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.