On 01.12.2014 at 12:20 in S1, there is the following noon lecture:
Old and new Transformations of Grammars: Structural, Algorithmic and Linguistic Applications
Formal grammars provide a rich combinatorial theory and useful applications. We consider primarily the context–free [CF] model, its sub-models and "mild" extensions as well. The known transformations, simple and subtle, between various forms of the grammars encompass much of the theory and the applications: parsing schemes in compiler's technology, homomorphisms theorems, hardest context-free languages and more.
Our novel scheme utilizes heavily the manner CFG derives its trees and terminal strings, graded by the derivation semi-order on the symbols. Essentially, alternate pairs of spread and rotate operations, which will be defined, enable transition from product of factors to union of components.
They create an operation-tree which transforms the original grammar at the root into a bunch of elongated thin threads at the leaves of the tree-namely
Webmaster: kamweb.mff.cuni.cz Modified: 25. 02. 2019