Publication Details

Synchronous Versions of Regulated Grammars: Generative Power and Linguistic Applications

HORÁČEK, P.; MEDUNA, A. Synchronous Versions of Regulated Grammars: Generative Power and Linguistic Applications. Theoretical and Applied Informatics, 2012, vol. 24, no. 3, p. 175-190. ISSN: 1896-5334.
Czech title
Synchronní verze řízených gramatik: generativní síla a lingvistické aplikace
Type
journal article
Language
English
Authors
Horáček Petr, Ing., Ph.D.
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
URL
Keywords

regulated grammar, synchronous grammar, generative power, natural language
translation

Abstract

This paper introduces the notion of new synchronous grammars as systems
consisting of two context-free grammars with linked rules instead of linked
nonterminals. Further, synchronous versions of regulated grammars, specifically,
matrix grammars and scattered context grammars, are discussed. From a theoretical
point of view, this paper discusses the power of these synchronous grammars. It
demonstrates the following main results. First, if we synchronize context-free
grammars by linking rules, the grammar generates the languages defined by matrix
grammars. Second, if we synchronize matrix grammars by linking matrices, the
generative power remains unchanged. Third, synchronous scattered context grammars
generate the class of recursively enumerable languages. From a more practical
viewpoint, this paper presents linguistic application prospects. The focus is on
natural language translation between Japanese and English.

Published
2012
Pages
175–190
Journal
Theoretical and Applied Informatics, vol. 24, no. 3, ISSN 1896-5334
DOI
10.2478/v10179-012-0011-6
BibTeX 
@article{BUT97006,
  author="Petr {Horáček} and Alexandr {Meduna}",
  title="Synchronous Versions of Regulated Grammars: Generative Power and Linguistic Applications",
  journal="Theoretical and Applied Informatics",
  year="2012",
  volume="24",
  number="3",
  pages="175--190",
  doi="10.2478/v10179-012-0011-6",
  issn="1896-5334",
  url="https://journals.pan.pl/tai/104548"
}
Back to top