Polynomial grammars with substitution

Speaker(s)

Janusz Schmude

Affiliation

MIM UW

Date

Nov. 18, 2020, 2:15 p.m.

Information about the event

online

Seminar

Seminar Automata Theory

---

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.

---