Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Teoria Automatów

 

Polynomial grammars with substitution


Prelegent: Janusz Schmude

2020-11-18 14:15

Polynomial grammars are grammars whose nonterminals generate tuples of integers (or elements of some ring in general) and productions use polynomial functions. They proved to be useful for proving decidability of equivalence of MSO transductions over strings and unordered trees and in general can be used for recursively defined functions on trees. In this talk we show two ways of adding substitution to polynomial grammar that preserve decidability of equivalence.