| Identifikační kód | RIV/61989100:27240/14:86092894 |
|---|
| Název v anglickém jazyce | Language equivalence of probabilistic pushdown automata |
|---|
| Druh | J - Článek v odborném periodiku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2014 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 2 |
|---|
| Počet tvůrců celkem | 4 |
|---|
| Počet domácích tvůrců | 1 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Vojtěch Forejt (státní příslušnost: GB - Spojené království Velké Británie a Severního Irska)
Petr Jančar (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 6026508)
Stefan Kiefer (státní příslušnost: GB - Spojené království Velké Británie a Severního Irska)
James Worrell (státní příslušnost: GB - Spojené království Velké Británie a Severního Irska) |
|---|
| Popis výsledku v anglickém jazyce | We study the language equivalence problem for probabilistic pushdown automata (pPDA) and their subclasses. We show that the problem is interreducible with the multiplicity equivalence problem for context-free grammars, the decidability of which has beenopen for several decades. Interreducibility also holds for pPDA with one control state. In contrast, for the case of a one-letter input alphabet we show that pPDA language equivalence (and hence multiplicity equivalence of context-free grammars) is in PSPACE and at least as hard as the polynomial identity testing problem. |
|---|
| Klíčová slova oddělená středníkem | probabilistic systems; language equivalence; Pushdown systems |
|---|
| Stránka www, na které se nachází výsledek | http://www.sciencedirect.com/science/article/pii/S0890540114000625 |
|---|
| DOI výsledku | 10.1016/j.ic.2014.04.003 |
|---|