The Containment Problem for Unambiguous Register Automata and Unambiguous Timed Automata
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10423144" target="_blank" >RIV/00216208:11320/21:10423144 - isvavai.cz</a>
Výsledek na webu
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=W6_ByXZaIc" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=W6_ByXZaIc</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00224-020-09997-2" target="_blank" >10.1007/s00224-020-09997-2</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
The Containment Problem for Unambiguous Register Automata and Unambiguous Timed Automata
Popis výsledku v původním jazyce
We investigate the complexity of the containment problem "Does L(A) SUBSET OF OR EQUAL TO L(B) hold?" for register automata and timed automata, where B is assumed to be unambiguous and A is arbitrary. We prove that the problem is decidable in the case of register automata over (N,=), in the case of register automata over (Q,<) when B has a single register, and in the case of timed automata when B has a single clock.We give a 2-EXPSPACE algorithm in the first case, whose complexity is a single exponential in the case that B has a bounded number of registers. In the other cases, we give an EXPSPACE algorithm.
Název v anglickém jazyce
The Containment Problem for Unambiguous Register Automata and Unambiguous Timed Automata
Popis výsledku anglicky
We investigate the complexity of the containment problem "Does L(A) SUBSET OF OR EQUAL TO L(B) hold?" for register automata and timed automata, where B is assumed to be unambiguous and A is arbitrary. We prove that the problem is decidable in the case of register automata over (N,=), in the case of register automata over (Q,<) when B has a single register, and in the case of timed automata when B has a single clock.We give a 2-EXPSPACE algorithm in the first case, whose complexity is a single exponential in the case that B has a bounded number of registers. In the other cases, we give an EXPSPACE algorithm.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
—
Návaznosti
R - Projekt Ramcoveho programu EK
Ostatní
Rok uplatnění
2021
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ů
Údaje specifické pro druh výsledku
Název periodika
Theory of Computing Systems [online]
ISSN
1433-0490
e-ISSN
—
Svazek periodika
2020
Číslo periodika v rámci svazku
2020
Stát vydavatele periodika
GB - Spojené království Velké Británie a Severního Irska
Počet stran výsledku
30
Strana od-do
—
Kód UT WoS článku
000570190700001
EID výsledku v databázi Scopus
2-s2.0-85091040673