On regular tree languages and deterministic pushdown automata
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F09%3A00158512" target="_blank" >RIV/68407700:21230/09:00158512 - isvavai.cz</a>
Nalezeny alternativní kódy
RIV/68407700:21240/09:00158512
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On regular tree languages and deterministic pushdown automata
Popis výsledku v původním jazyce
The theory of formal string languages and of formal tree languages are both important parts of the theory of formal languages.Regular tree languages are recognized by finite tree automata.Trees in their postfix notation can be seen as strings.This paperpresents a simple transformation from any given finite tree automaton recognizing a regular tree language to a deterministic pushdown automaton accepting the same tree language in postfix notation.The resulting deterministic pushdown automaton can be implemented easily by an existing parser generator because it is constructed for an LR(0) grammar, and its size directly corresponds to the size of the deterministic finite tree automaton. The class of regular tree languages in postfix notation is a propersubclass of deterministic context-free string languages. Moreover, the class of tree languages which are in their postfix notation deterministic context-free string languages is a proper superclass of the class of regular tree languages.
Název v anglickém jazyce
On regular tree languages and deterministic pushdown automata
Popis výsledku anglicky
The theory of formal string languages and of formal tree languages are both important parts of the theory of formal languages.Regular tree languages are recognized by finite tree automata.Trees in their postfix notation can be seen as strings.This paperpresents a simple transformation from any given finite tree automaton recognizing a regular tree language to a deterministic pushdown automaton accepting the same tree language in postfix notation.The resulting deterministic pushdown automaton can be implemented easily by an existing parser generator because it is constructed for an LR(0) grammar, and its size directly corresponds to the size of the deterministic finite tree automaton. The class of regular tree languages in postfix notation is a propersubclass of deterministic context-free string languages. Moreover, the class of tree languages which are in their postfix notation deterministic context-free string languages is a proper superclass of the class of regular tree languages.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GA201%2F09%2F0807" target="_blank" >GA201/09/0807: Analýza a zpracování řetězců a stromů</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2009
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
Acta Informatica
ISSN
0001-5903
e-ISSN
—
Svazek periodika
46
Číslo periodika v rámci svazku
7
Stát vydavatele periodika
DE - Spolková republika Německo
Počet stran výsledku
15
Strana od-do
—
Kód UT WoS článku
000270738700003
EID výsledku v databázi Scopus
—