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

Result code in 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>

Result on the web

<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

—

Result language

angličtina

Original language name

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

Original language description

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

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

IN - Informatics

OECD FORD branch

—

Project

<a href="/en/project/MEB041003" target="_blank" >MEB041003: Context-free languages and pushdown automata</a><br>

Continuities

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

Publication year

2012

Confidentiality

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

Name of the periodical

Mathematics for applications

ISSN

1805-3610

e-ISSN

—

Volume of the periodical

1

Issue of the periodical within the volume

1

Country of publishing house

CZ - CZECH REPUBLIC

Number of pages

22

Pages from-to

13-35

UT code for WoS article

—

EID of the result in the Scopus database

—