Journal article

HORÁČEK Petr and MEDUNA Alexander. Synchronous Versions of Regulated Grammars: Generative Power and Linguistic Applications. Theoretical and Applied Informatics. Varšava: 2012, vol. 24, no. 3, pp. 175-190. ISSN 1896-5334. Available from:
Publication language:english
Original title:Synchronous Versions of Regulated Grammars: Generative Power and Linguistic Applications
Title (cs):Synchronní verze řízených gramatik: generativní síla a lingvistické aplikace
Journal:Theoretical and Applied Informatics, Vol. 24, No. 3, Varšava, PL
regulated grammar, synchronous grammar, generative power, natural language translation
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.
   author = {Petr Hor{\'{a}}{\v{c}}ek and Alexander Meduna},
   title = {Synchronous Versions of Regulated Grammars:
	Generative Power and Linguistic Applications},
   pages = {175--190},
   journal = {Theoretical and Applied Informatics},
   volume = 24,
 number = 3,
   year = 2012,
   ISSN = {1896-5334},
   doi = {10.2478/v10179-012-0011-6},
   language = {english},
   url = {}

Your IPv4 address:
Switch to https