Detail publikace

Multigenerative Grammar Systems and Matrix Grammars

Originální název

Multigenerative Grammar Systems and Matrix Grammars

Anglický název

Multigenerative Grammar Systems and Matrix Grammars

Jazyk

en

Originální abstrakt

Multigenerative grammar systems are based on cooperating context-free grammatical components that simultaneously generate their strings in a  rule-controlled or nonterminal-controlled rewriting way, and after this simultaneous generation is completed, all the generated terminal strings are combined together by some common string operations, such as concatenation, and placed into the generated languages of these systems. The present paper proves that these systems are equivalent with the matrix grammars. In addition, we demonstrate that these systems with any number of grammatical components can be transformed to equivalent two-component versions of these systems. The paper points out that if these systems work in the leftmost rewriting way, they are more powerful than the systems working in a general way.

Anglický abstrakt

Multigenerative grammar systems are based on cooperating context-free grammatical components that simultaneously generate their strings in a  rule-controlled or nonterminal-controlled rewriting way, and after this simultaneous generation is completed, all the generated terminal strings are combined together by some common string operations, such as concatenation, and placed into the generated languages of these systems. The present paper proves that these systems are equivalent with the matrix grammars. In addition, we demonstrate that these systems with any number of grammatical components can be transformed to equivalent two-component versions of these systems. The paper points out that if these systems work in the leftmost rewriting way, they are more powerful than the systems working in a general way.

BibTex


@article{BUT50887,
  author="Roman {Lukáš} and Alexandr {Meduna}",
  title="Multigenerative Grammar Systems and Matrix Grammars",
  annote="Multigenerative grammar systems are based on cooperating context-free grammatical
components that simultaneously generate their strings in a  rule-controlled or
nonterminal-controlled rewriting way, and after this simultaneous generation is
completed, all the generated terminal strings are combined together by some
common string operations, such as concatenation, and placed into the generated
languages of these systems. The present paper proves that these systems are
equivalent with the matrix grammars. In addition, we demonstrate that these
systems with any number of grammatical components can be transformed to
equivalent two-component versions of these systems. The paper points out that if
these systems work in the leftmost rewriting way, they are more powerful than the
systems working in a general way.",
  address="NEUVEDEN",
  chapter="50887",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  journal="Kybernetika",
  number="1",
  volume="46",
  year="2010",
  month="december",
  pages="68--82",
  publisher="NEUVEDEN",
  type="journal article in Scopus"
}