Detail publikace

Simple Matrix Grammars and Their Leftmost Variants

MEDUNA, A. SOUKUP, O.

Originální název

Simple Matrix Grammars and Their Leftmost Variants

Anglický název

Simple Matrix Grammars and Their Leftmost Variants

Jazyk

en

Originální abstrakt

In essence, simple matrix grammars can be seen as sequences of context-free grammars, referred to as their components, which work in parallel. The present paper demonstrates that two-component simple matrix grammars are as powerful as ordinary matrix grammars. Then, it places three leftmost derivation restrictions upon these grammars and demonstrates that under two of these restrictions, simple matrix grammars are computational complete--that is, they are equivalent with Turing machines. From a historical perspective, concerning simple matrix grammars, the paper also makes several remarks that correct false statements published about them in the past.

Anglický abstrakt

In essence, simple matrix grammars can be seen as sequences of context-free grammars, referred to as their components, which work in parallel. The present paper demonstrates that two-component simple matrix grammars are as powerful as ordinary matrix grammars. Then, it places three leftmost derivation restrictions upon these grammars and demonstrates that under two of these restrictions, simple matrix grammars are computational complete--that is, they are equivalent with Turing machines. From a historical perspective, concerning simple matrix grammars, the paper also makes several remarks that correct false statements published about them in the past.

Dokumenty

BibTex


@article{BUT130903,
  author="Alexandr {Meduna} and Ondřej {Soukup}",
  title="Simple Matrix Grammars and Their Leftmost Variants",
  annote="
In essence, simple matrix grammars can be seen as sequences of context-free
grammars, referred to as their components, which work in parallel. The present
paper demonstrates that two-component simple matrix grammars are as powerful as
ordinary matrix grammars. Then, it places three leftmost derivation restrictions
upon these grammars and demonstrates that under two of these restrictions, simple
matrix grammars are computational complete--that is, they are equivalent with
Turing machines. From a historical perspective, concerning simple matrix
grammars, the paper also makes several remarks that correct false statements
published about them in the past.",
  address="NEUVEDEN",
  chapter="130903",
  doi="10.1142/S0129054116400141",
  edition="NEUVEDEN",
  howpublished="online",
  institution="NEUVEDEN",
  number="3",
  volume="27",
  year="2016",
  month="june",
  pages="359--373",
  publisher="NEUVEDEN",
  type="journal article in Web of Science"
}