Thesis Details
Grammars with Restricted Derivation Trees
This doctoral thesis studies theoretical properties of grammars with restricted derivation trees. After presenting the state of the art concerning this investigation area, the research is focused on the three main kinds of the restrictions placed upon the derivation trees. First, it introduces completely new investigation area represented by cut-based restriction and examines the generative power of the grammars restricted in this way. Second, it investigates several new properties of path-based restriction placed upon the derivation trees. Specifically, it studies the impact of erasing productions on the generative power of grammars with restricted path and introduces two corresponding normal forms. Then, it describes a new relation between grammars with restricted path and some pseudoknots. Next, it presents a counterargument to the generative power of grammars with controlled path that has been considered as well-known so far. Finally, it introduces a generalization of path-based restriction to not just one but several paths. The model generalized in this way is studied, namely its pumping, closure, and parsing properties.
tree controlled grammars, level controlled grammars, path controlled grammars, paths controlled grammars, cut controlled grammars, ordered cut controlled grammars, regulated rewriting, restricted derivation trees
@phdthesis{FITPT355,
author = "Ji\v{r}\'{i} Koutn\'{y}",
type = "Ph.D. thesis",
title = "Grammars with Restricted Derivation Trees",
school = "Brno University of Technology, Faculty of Information Technology",
year = 2012,
location = "Brno, CZ",
language = "english",
url = "https://www.fit.vut.cz/study/phd-thesis/355/"
}