Quantitative Versions of the Chomsky-Schützenberger Theorem

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Quantitative Versions of the Chomsky-Schützenberger Theorem

Vortrag von Pavlos Marantidis
The emergence of weighted structures in Formal Language Theory naturally gave rise to questions whether classical results hold in more general environments. The Chomsky-Schützenberger Theorem (1963) states that any context-free language (CFL) can be represented by two simpler languages, a regular and a Dyck language. Droste and Vogler (2013) derived such a theorem for the abstract structure of unital valuation monoids. In this talk, these constructions, in addition to a similar approach for stochastic CFLs will be presented.