Publication detail

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

MEDUNA, A. ČERMÁK, M. HORÁČEK, P.

Original Title

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

English Title

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

Type

journal article - other

Language

en

Original Abstract

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 context-free 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 Japanese-Czech translation.

English abstract

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 context-free 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 Japanese-Czech translation.

Keywords

n-languages, transducer, computational control

RIV year

2012

Released

19.03.2012

Publisher

NEUVEDEN

Location

NEUVEDEN

Pages from

13

Pages to

35

Pages count

22

URL

BibTex


@article{BUT96944,
  author="Alexandr {Meduna} and Martin {Čermák} and Petr {Horáček}",
  title="Rule-restricted automaton-grammar transducers: Power and linguistic applications",
  annote="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 context-free 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
Japanese-Czech translation.",
  address="NEUVEDEN",
  chapter="96944",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  number="1",
  volume="1",
  year="2012",
  month="march",
  pages="13--35",
  publisher="NEUVEDEN",
  type="journal article - other"
}