Journal articleČERMÁK Martin, HORÁČEK Petr and MEDUNA Alexander. Rulerestricted automatongrammar transducers: Power and linguistic applications. Mathematics for Applications. Brno: Department of Mathematics FEEC BUT, 2012, vol. 1, no. 1, pp. 1335. ISSN 18053610. Available from: http://ma.fme.vutbr.cz/archiv/1_1/13_35.pdf  Publication language:  english 

Original title:  Rulerestricted automatongrammar transducers: Power and linguistic applications 

Title (cs):  Pravidly omezený automatověgramatický převodník: síla a lingvistické aplikace 

Pages:  1335 

Place:  CZ 

Year:  2012 

URL:  http://ma.fme.vutbr.cz/archiv/1_1/13_35.pdf 

Journal:  Mathematics for Applications, Vol. 1, No. 1, Brno, CZ 

ISSN:  18053610 

Keywords 

nlanguages, transducer, computational control 
Annotation 

This paper introduces the notion of a new transducer as a twocomponent system, which consists of a finite automaton and a contextfree 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 multicounter automata, respectively. Second, if we place a leftmost restriction on derivation in the contextfree grammar, both accepting and generating power of the system is equal to generative power of contextfree grammars. Third, the system with appearance checking can accept and generate all recursively enumerable languages. From more pragmatical viewpoint, this paper describes several linguistic applications. A special attention is paid to the JapaneseCzech translation. 
BibTeX: 

@ARTICLE{
author = {Martin {\v{C}}erm{\'{a}}k and Petr Hor{\'{a}}{\v{c}}ek and
Alexander Meduna},
title = {Rulerestricted automatongrammar transducers: Power and
linguistic applications},
pages = {1335},
journal = {Mathematics for Applications},
volume = {1},
number = {1},
year = {2012},
ISSN = {18053610},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9957}
} 
