Thursday, 24 Nov. 2005, 14:00
Cybernetica Bldg (Akadeemia tee 21), room B101
Slides from the talk [pdf]
Abstract: We present a method for size reduction of two-way multitape automata. Our algorithm applies local transformations that change the order in which transitions concerning different tapes occur in the automaton graph, and merge suitable states into a single state. Our work is motivated by implementation of a language for string manipulation in database systems where string predicates are compiled into two-way multitape automata. Additionally, we present a (one-tape) NFA reduction algorithm that is based on a method proposed for DFA minimization by Kameda and Weiner, and apply this algorithm, combined with the multitape automata reduction algorithm, on our multitape automata.
(Joint work with Matti Nykänen and Esko Ukkonen at the University of Helsinki, presented at CIAA 2005, to be published in LNCS 3845.)