Publication detail

One-Sided Random Context Grammars

MEDUNA, A. ZEMEK, P.

Original Title

One-Sided Random Context Grammars

Type

journal article - other

Language

English

Original Abstract

The notion of a one-sided random context grammar is defined as a context-free-based regulated grammar, in which a set of permitting symbols and a set of forbidding symbols are attached to every rule, and its set of rules is divided into the set of left random context rules and the set of right random context rules. A left random context rule can rewrite a nonterminal if each of its permitting symbols occurs to the left of the rewritten symbol in the current sentential form while each of its forbidding symbols does not occur there. A right random context rule is applied analogically except that the symbols are examined to the right of the rewritten symbol. The paper demonstrates that without erasing rules, one-sided random context grammars characterize the family of context-sensitive languages, and with erasing rules, these grammars characterize the family of recursively enumerable languages. In fact, these characterization results hold even if the set of left random context rules coincides with the set of right random context rules. Several special cases of these grammars are considered, and their generative power is established. In its conclusion, some important open problems are suggested to study in the future.

Keywords

Regulated rewriting, random context grammars, one-sided variants, generative power, language families

Authors

MEDUNA, A.; ZEMEK, P.

RIV year

2011

Released

21. 4. 2011

ISBN

0001-5903

Periodical

Acta Informatica

Year of study

48

Number

3

State

Federal Republic of Germany

Pages from

149

Pages to

163

Pages count

15

URL

http://www.springerlink.com/content/c70163w7764u8660/

BibTex

@article{BUT49880,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="One-Sided Random Context Grammars",
  journal="Acta Informatica",
  year="2011",
  volume="48",
  number="3",
  pages="149--163",
  doi="10.1007/s00236-011-0134-y",
  issn="0001-5903",
  url="http://www.springerlink.com/content/c70163w7764u8660/"
}