Reducing Deep Pushdown Automata and Infinite Hierarchy

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F06%3APU66982" target="_blank" >RIV/00216305:26230/06:PU66982 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Reducing Deep Pushdown Automata and Infinite Hierarchy

Original language description

This contribution presents reducing variant of the deep pushdown automata.<br>Deep pushdown automata is a new generalization of the classical pushdown automata.<br>The basic idea of the modification consists of allowing these automata to access more deeper parts of pushdown<br>and reducing strings to non-input symbols in the pushdown.<br>It works similarly to bottom-up analysis simulation of context-free grammars in the classical pushdown automata<br>except it reads the input from the right to the left.<br>Further, this paper presents results concerning the equivalence of reducing deep pushdown automata with <i>n</i>-limited state grammars<br>and infinite hierarchy of language families based on that and one open problem.

Czech name

Redukující hluboké zásobníkové automaty a nekonečná hierarchie

Czech description

<div>Příspěvek prezentuje redukující variantu hlubokých zásobníkových automatů. Hluboké zásobníkové automaty jsou nové zobecnění klasického zásobníkového automatu. Základní myšlenka modifikace se skládá s umožnění&nbsp;těmto automatům přistupovat hlouběji do zásobníku a tam redukovat neprázdné řetězce na nevstupní symboly. Princip je podobný analýze zdola nahoru simulující bezkontextovou gramatiku prostřednictvím klasického zásobníkového automatu až na to, že čteme vstup zprava doleva.<br>Dále článek prezentuje výsledky o ekvivalenci redukujících zásobníkových automatů s <i>n</i>-limitovanými stavovými gramatikami a o nekonečné hierarchii na této ekvivalenci založené. V závěru zmiňuje modifikace a otevřený problém.</div>

Type

D - Article in proceedings

CEP classification

JC - Computer hardware and software

OECD FORD branch

—

Project

<a href="/en/project/GA201%2F04%2F0441" target="_blank" >GA201/04/0441: Optimally integrated models of modern information technologies</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2006

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

MEMICS 2006 Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science

ISBN

80-214-3287-X

ISSN

—

e-ISSN

—

Number of pages

8

Pages from-to

214-221

Publisher name

Faculty of Information Technology BUT

Place of publication

Mikulov

Event location

Mikulov

Event date

Oct 27, 2006

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—