Efficient separability of regular languages by subsequences and suffixes

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F13%3A00394007" target="_blank" >RIV/67985840:_____/13:00394007 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-642-39212-2_16" target="_blank" >http://dx.doi.org/10.1007/978-3-642-39212-2_16</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-39212-2_16" target="_blank" >10.1007/978-3-642-39212-2_16</a>

Jazyk výsledku
angličtina
Název v původním jazyce
Efficient separability of regular languages by subsequences and suffixes
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Efficient separability of regular languages by subsequences and suffixes
Popis výsledku anglicky
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.

Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění
2013
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)