Quantitative Versions of the Chomsky-Schützenberger Theorem
From International Center for Computational Logic
Quantitative Versions of the Chomsky-Schützenberger Theorem
Talk by Pavlos Marantidis
- Location: ABP 3105
- Start: 3. December 2015 at 1:45 pm
- End: 3. December 2015 at 2:45 pm
- Research group: Automata Theory
- Event series: KBS Seminar
- iCal
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.
