Rule-restricted automaton-grammar tranduscers: Power and linguistic applications

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F12%3APU101769" target="_blank" >RIV/00216305:26230/12:PU101769 - isvavai.cz</a>

Výsledek na webu

<a href="http://ma.fme.vutbr.cz/archiv/1_1/13_35.pdf" target="_blank" >http://ma.fme.vutbr.cz/archiv/1_1/13_35.pdf</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Rule-restricted automaton-grammar tranduscers: Power and linguistic applications

Popis výsledku v původním jazyce

This paper introduces the notion of a new transducer as a two-component system, which consists of a finite automaton and a context-free grammar. In essence, while the automaton reads its input string, the grammar produces its output string, and their cooperation is controlled by a set, which restricts the usage of their rules. From a theoretical viewpoint, the present paper discusses the power of this system working in an ordinary way as well as in a leftmost way. In addition, the paper introduces an appearance checking, which allows us to check whether some symbols are present in the rewritten string, and studies its effect on the power. It achieves the following three main results. First, the system generates and accepts languages defined by matrix grammars and partially blind multi-counter automata, respectively. Second, if we place a leftmost restriction on derivation in the context-free grammar, both accepting and generating power of the system is equal to generative power of cont

Název v anglickém jazyce

Rule-restricted automaton-grammar tranduscers: Power and linguistic applications

Popis výsledku anglicky

This paper introduces the notion of a new transducer as a two-component system, which consists of a finite automaton and a context-free grammar. In essence, while the automaton reads its input string, the grammar produces its output string, and their cooperation is controlled by a set, which restricts the usage of their rules. From a theoretical viewpoint, the present paper discusses the power of this system working in an ordinary way as well as in a leftmost way. In addition, the paper introduces an appearance checking, which allows us to check whether some symbols are present in the rewritten string, and studies its effect on the power. It achieves the following three main results. First, the system generates and accepts languages defined by matrix grammars and partially blind multi-counter automata, respectively. Second, if we place a leftmost restriction on derivation in the context-free grammar, both accepting and generating power of the system is equal to generative power of cont

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/MEB041003" target="_blank" >MEB041003: Bezkontextové gramatiky a zásobníkové automaty</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2012

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ů

Název periodika

Mathematics for applications

ISSN

1805-3610

e-ISSN

—

Svazek periodika

1

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

CZ - Česká republika

Počet stran výsledku

22

Strana od-do

13-35

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—