Header menu link for other important links
X
Time Varying Finite Automata
Kamala Krithivasan, Anindya Das
Published in
1986
Volume: 19
   
Issue: 2
Pages: 103 - 123
Abstract
In this paper, we consider two machine models equivalent in power to Turing machines. Time varying finite automata are defined and it is shown that time varying nondeterministic finite automata are equivalent to time varying deterministic finite automata. But, we find that, when e-moves are introduced, the power is increased to that of Turing machines. Equivalence between time varying regular grammars [6] and time varying nondeterministic finite automata with s-moves is shown. We also consider time varying generalized finite automata and show their equivalence to terminal weighted regular grammars [5], thus proving that time varying generalized finite automata have the same power as Turing machines. © 1986, Taylor & Francis Group, LLC. All rights reserved.
About the journal
JournalInternational Journal of Computer Mathematics
ISSN00207160
Open AccessNo