Detail publikace

Left Random Context ET0L Grammars

MEDUNA, A. ZEMEK, P.

Originální název

Left Random Context ET0L Grammars

Typ

článek v časopise - ostatní, Jost

Jazyk

angličtina

Originální abstrakt

Consider ET0L grammars. Modify them such that a set of permitting symbols and a set of forbidding symbols are attached to each of their rules, just like in random context grammars. A rule like this can rewrite a symbol if each of its permitting symbols occurs to the left of the symbol to be rewritten in the current sentential form while each of its forbidding symbols does not occur there. ET0L grammars modified in this way are referred to as left random context ET0L grammars, and they represent the principal subject of the investigation in this paper. We prove that these grammars characterize the family of recursively enumerable languages, and without erasing rules, they characterize the family of context-sensitive languages. We also introduce a variety of special cases of these grammars and establish their generative power. In the conclusion, we put all the achieved results into the context of formal language theory as a whole and formulate several open questions.

Klíčová slova

Regulated rewriting; ET0L grammars; random context; left variants; generative power; language families

Autoři

MEDUNA, A.; ZEMEK, P.

Rok RIV

2013

Vydáno

1. 5. 2013

ISSN

0169-2968

Periodikum

Fundamenta Informaticae

Ročník

123

Číslo

3

Stát

Polská republika

Strany od

289

Strany do

304

Strany počet

16

URL

http://iospress.metapress.com/content/b3h6456215g6754p/?p=e7359885e380461c96f9663f43ae8b09&pi=2

BibTex

@article{BUT103402,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="Left Random Context ET0L Grammars",
  journal="Fundamenta Informaticae",
  year="2013",
  volume="123",
  number="3",
  pages="289--304",
  doi="10.3233/FI-2013-811",
  issn="0169-2968",
  url="http://iospress.metapress.com/content/b3h6456215g6754p/?p=e7359885e380461c96f9663f43ae8b09&pi=2"
}