Detail publikace

One-Sided Random Context Grammars: A Survey

Originální název

One-Sided Random Context Grammars: A Survey

Anglický název

One-Sided Random Context Grammars: A Survey

Jazyk

en

Originální abstrakt

Recall that the notion of a one-sided random context grammar is based upon a finite set of context-free rules, each of which may be extended by finitely many permitting and forbidding nonterminal symbols. The set of all these rules is divided into two sets - the set of left random context rules and the set of right random context rules. When applying a left random context rule, the grammar checks the existence and absence of its permitting and forbidding symbols, respectively, in the prefix to the left of the rewritten nonterminal. Analogically, when applying a right random context rule, it checks the existence and absence of its permitting and forbidding symbols, respectively, only in the suffix to the right of the rewritten nonterminal. This paper gives a survey of the established results concerning one-sided random context grammars. These results concern their generative power, normal forms, size reduction, and conceptual modifications, which represent both restricted and generalized versions of their standard concepts. Perhaps most importantly and surprisingly, the paper points out that propagating versions of one-sided random context grammars characterize the family of context-sensitive languages, and with erasing rules, they characterize the family of recursively enumerable languages; as a result, they are stronger than ordinary random context grammars. Many open problem areas are suggested.

Anglický abstrakt

Recall that the notion of a one-sided random context grammar is based upon a finite set of context-free rules, each of which may be extended by finitely many permitting and forbidding nonterminal symbols. The set of all these rules is divided into two sets - the set of left random context rules and the set of right random context rules. When applying a left random context rule, the grammar checks the existence and absence of its permitting and forbidding symbols, respectively, in the prefix to the left of the rewritten nonterminal. Analogically, when applying a right random context rule, it checks the existence and absence of its permitting and forbidding symbols, respectively, only in the suffix to the right of the rewritten nonterminal. This paper gives a survey of the established results concerning one-sided random context grammars. These results concern their generative power, normal forms, size reduction, and conceptual modifications, which represent both restricted and generalized versions of their standard concepts. Perhaps most importantly and surprisingly, the paper points out that propagating versions of one-sided random context grammars characterize the family of context-sensitive languages, and with erasing rules, they characterize the family of recursively enumerable languages; as a result, they are stronger than ordinary random context grammars. Many open problem areas are suggested.

BibTex


@inbook{BUT111524,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="One-Sided Random Context Grammars: A Survey",
  annote="Recall that the notion of a one-sided random context grammar is based upon
a finite set of context-free rules, each of which may be extended by finitely
many permitting and forbidding nonterminal symbols. The set of all these rules is
divided into two sets - the set of left random context rules and the set of right
random context rules. When applying a left random context rule, the grammar
checks the existence and absence of its permitting and forbidding symbols,
respectively, in the prefix to the left of the rewritten nonterminal.
Analogically, when applying a right random context rule, it checks the existence
and absence of its permitting and forbidding symbols, respectively, only in the
suffix to the right of the rewritten nonterminal.

This paper gives a survey of the established results concerning one-sided random
context grammars. These results concern their generative power, normal forms,
size reduction, and conceptual modifications, which represent both restricted and
generalized versions of their standard concepts. Perhaps most importantly and
surprisingly, the paper points out that propagating versions of one-sided random
context grammars characterize the family of context-sensitive languages, and with
erasing rules, they characterize the family of recursively enumerable languages;
as a result, they are stronger than ordinary random context grammars. Many open
problem areas are suggested.",
  address="Springer Verlag",
  booktitle="Computing with New Resources",
  chapter="111524",
  doi="10.1007/978-3-319-13350-8_25",
  edition="NEUVEDEN",
  howpublished="print",
  institution="Springer Verlag",
  year="2014",
  month="december",
  pages="338--351",
  publisher="Springer Verlag",
  type="book chapter"
}