Random Context and Programmed Grammars of Finite Index Have The Same Generative Power

Type

conference paper

Language

English

Authors

Křivka Zbyněk, Ing., Ph.D., DIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)

Abstract

The question of whether for every programmed grammar of index k, there is an equivalent a random context grammar in which every production has no forbidding context represents an open problem in the formal language theory. This paper solves this problem by establishing this equivalence.

Keywords

random context grammars, permitting grammars, programmed grammars, finite index, generative power

Annotation

The question of whether for every programmed grammar of index k, there is an equivalent a random context grammar in which every production has no forbidding context represents an open problem in the formal language theory. This paper solves this problem by establishing this equivalence.

Published

2005

Pages

67–72

Proceedings

Proceedings of 8th International Conference ISIM'05 Information Systems Implementation and Modelling

Series

1st edition

Conference

8th International Conference on Information Systems Implementation and Modelling

ISBN

80-86840-09-3

Publisher

Marq software s.r.o.

Place

Ostrava

BibTeX

@inproceedings{BUT21455,
  author="Zbyněk {Křivka} and Alexandr {Meduna}",
  title="Random Context and Programmed Grammars of Finite Index Have The Same Generative Power",
  booktitle="Proceedings of 8th International Conference ISIM'05 Information Systems Implementation and Modelling",
  year="2005",
  series="1st edition",
  pages="67--72",
  publisher="Marq software s.r.o.",
  address="Ostrava",
  isbn="80-86840-09-3"
}

Projects

Optimally Integrated Models of Modern Information Technologies, GACR, Standardní projekty, GA201/04/0441, start: 2004-01-01, end: 2006-12-31, completed

Research groups

Formal Model Research Group (RG FM)

Departments

Department of Information Systems (DIFS)