Languages over Commutative Alphabets (part 2)

Prelegent(ci)

Eryk Kopczyński (Uniwersytet Warszawski)

Afiliacja

Uniwersytet Warszawski

Termin

21 października 2009 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

We consider languages accepted by non-deterministic finite automata and context-free grammars, except that we treat the language in a commutative way: we do not care about the order of letters in the accepted word, but rather how many times each one of them appears. In this setting, usual problems, like membership and equality, have different complexities than in the non-commutative case. In most cases we assume that the alphabet is of fixed size, and sometimes even of size 1 or 2. We show tight complexity bounds for those problems.

---