Languages over Commutative Alphabets

Speaker(s)

Eryk Kopczyński

Affiliation

Uniwersytet Warszawski

Date

Oct. 14, 2009, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---