Thesis Details
Formal Models of Distributed Computation
The present thesis introduces derivation trees for several different types of grammars in generalized Kuroda normal forms; namely, general, regular-controlled, and scattered context grammars and cooperating distributed grammar systems. It defines simple tree-based properties related to non-context-free properties of all grammars in question and shows that if there exists a limiting constant k such that every sentence in the generated language L is the frontier of a derivation tree in which the number of occurrences of the defined tree-based properties is limited by k, the language L is in fact context-free. The thesis explains that this result represents a powerful tool for showing languages to be context-free. It also provides illustrations and examples which sketch how to apply this tool in practice.
General grammars, regular-controlled context-free grammars, scattered context grammars, cooperating distributed grammar systems, normal forms, derivation trees, restricted derivation trees, context-freeness, context-freeness of finite index.
@phdthesis{FITPT691,
author = "Ond\v{r}ej Soukup",
type = "Ph.D. thesis",
title = "Formal Models of Distributed Computation",
school = "Brno University of Technology, Faculty of Information Technology",
year = 2017,
location = "Brno, CZ",
language = "english",
url = "https://www.fit.vut.cz/study/phd-thesis/691/"
}