On size reduction techniques for multitape automata

Autor: Esko Ukkonen, Matti Nykänen, Hellis Tamm
Rok vydání: 2006
Předmět:
Multitape automata
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
Theoretical computer science
General Computer Science
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Theoretical Computer Science
Reduction (complexity)
DFA minimization
0202 electrical engineering
electronic engineering
information engineering
Nondeterministic finite automaton
Mathematics
Finite-state machine
Quantitative Biology::Neurons and Cognition
Size reduction
String (computer science)
Nonlinear Sciences::Cellular Automata and Lattice Gases
Automaton
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
010201 computation theory & mathematics
Nondeterministic finite automata
Graph (abstract data type)
020201 artificial intelligence & image processing
State (computer science)
Algorithm
Computer Science::Formal Languages and Automata Theory
Computer Science(all)
Zdroj: Theoretical Computer Science. 363:234-246
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2006.07.027
Popis: 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. Empirical results on the performance of our method when applied on some multitape automata originating from string predicates are reported.
Databáze: OpenAIRE
Externí odkaz: