TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 13.02.2013

isti-logo

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

The Complexity of Intersecting Finite Automata Having Few Final States

Dr. Andreas Krebs (Eberhard Karls Universität Tübingen)

The problem of determining whether several finite automata accept a word in common is closely related to the well-studied membership problem in transformation monoids. We raise the issue of limiting the number of final states in the automata intersection problem. For automata with two final states, we show the problem to be ?L-complete or NP-complete according to whether a nontrivial monoid other than a direct product of cyclic groups of order 2 is allowed in the automata. We further consider idempotent commutative automata and (abelian, mainly) group automata with one, two or three final states over a singleton or larger alphabet, elucidating the complexity of the intersection nonemptiness and related problems in each case.

(This is joint work with Michael Blondin and Pierre McKenzie.)

Date
Speaker
Location
Language
13.02.2013 10:30
Andreas Krebs
TEL 512
german/english

Back to the research colloquium site.

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe