Nie jesteś zalogowany | Zaloguj się

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.