Finite automata with multiplication |
| |
| Authors: | Oscar H Ibarra Sartaj K Sahni Chul E Kim |
| |
| Affiliation: | Department of Computer Science, University of Minnesota, Minneapolis, MN 55455, U.S.A. |
| |
| Abstract: | A finite automaton with multiplication (FAM) is a finite automaton with a register which is capable of holding any positive rational number. The register can be multiplied by any of a fixed number of rationals and can be tested for value 1. Closure properties and decision problems for various types of FAM's (e.g. two-way, one-way, nondeterministic, deterministic) are investigated. In particular, it is shown that the languages recognized by two-way deterministic FAM's are of tape complexity log n and time complexity n3. Some decision problems related to vector addition systems are also studied. |
| |
| Keywords: | Present address: University of Maryland College Park MD 20742 U S A |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
