Detail publikace

Workspace Theorems for Regular-Controlled Grammars

Originální název

Workspace Theorems for Regular-Controlled Grammars

Anglický název

Workspace Theorems for Regular-Controlled Grammars

Jazyk

en

Originální abstrakt

This paper establishes a workspace theorem in terms of regular-controlled (context-free) grammars. It proves that, if, for a regular-controlled grammar H, there is a positive integer k such that H generates every sentence y in L(H) by a derivation in which every sentential form x contains at most (k-1)|x|/k occurrences of nonterminals that are erased throughout the rest of the derivation, where |x| denotes the length of x, then the language of H is generated by a propagating regular-controlled grammar. An analogical workspace theorem is demonstrated for regular-controlled grammars with appearance checking. The paper provides an algorithm that removes all erasing rules from any regular-controlled grammar (possibly with appearance checking) that satisfies the workspace condition above without affecting the generated language. In its conclusion, the paper points out a relationship of the workspace theorems to other areas of formal language theory.

Anglický abstrakt

This paper establishes a workspace theorem in terms of regular-controlled (context-free) grammars. It proves that, if, for a regular-controlled grammar H, there is a positive integer k such that H generates every sentence y in L(H) by a derivation in which every sentential form x contains at most (k-1)|x|/k occurrences of nonterminals that are erased throughout the rest of the derivation, where |x| denotes the length of x, then the language of H is generated by a propagating regular-controlled grammar. An analogical workspace theorem is demonstrated for regular-controlled grammars with appearance checking. The paper provides an algorithm that removes all erasing rules from any regular-controlled grammar (possibly with appearance checking) that satisfies the workspace condition above without affecting the generated language. In its conclusion, the paper points out a relationship of the workspace theorems to other areas of formal language theory.

BibTex


@article{BUT76319,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="Workspace Theorems for Regular-Controlled Grammars",
  annote="This paper establishes a workspace theorem in terms of regular-controlled
(context-free) grammars. It proves that, if, for a regular-controlled grammar H,
there is a positive integer k such that H generates every sentence y in L(H) by
a derivation in which every sentential form x contains at most (k-1)|x|/k
occurrences of nonterminals that are erased throughout the rest of the
derivation, where |x| denotes the length of x, then the language of H is
generated by a propagating regular-controlled grammar. An analogical workspace
theorem is demonstrated for regular-controlled grammars with appearance checking.
The paper provides an algorithm that removes all erasing rules from any
regular-controlled grammar (possibly with appearance checking) that satisfies the
workspace condition above without affecting the generated language. In its
conclusion, the paper points out a relationship of the workspace theorems to
other areas of formal language theory.",
  address="NEUVEDEN",
  chapter="76319",
  doi="10.1016/j.tcs.2011.04.042",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  number="35",
  volume="412",
  year="2011",
  month="august",
  pages="4604--4612",
  publisher="NEUVEDEN",
  type="journal article in Web of Science"
}