𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Multitape finite automata with rewind instructions

✍ Scribed by Arnold L. Rosenberg

Publisher
Elsevier Science
Year
1967
Tongue
English
Weight
858 KB
Volume
1
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

The model of multitape finite automaton is generalized by allowing the automaton to rewind all its tapes simultaneously at any stage in its computation. This added capability is shown to yield the Boolean closure of the class of word relations defined by multitape finite automata. Several properties of this extended model are investigated. In particular it is shown that this model is incomparable to the nondeterministic multitape finite automata and is strictly weaker than two-way multitape finite automata.

πŸ“œ SIMILAR VOLUMES

VC-dimensions of finite automata and com
VC-dimensions of finite automata and commutative finite automata with k letters and n states
✍ Yoshiyasu Ishigami; Sei'ichi Tani πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 706 KB

An investigation is conducted of the Vapnik-Chervonenkis dimensions (VC-dimensions) of finite automata having k letters and n states. It is shown for a fixed positive integer k( 22) that (1) the VC-dimension of DFAk(n) := {Lc{1,2,...,k}\* : some deterministic finite automaton with at most n states a

VC-dimensions of finite automata and com
VC-dimensions of finite automata and commutative finite automata with k letters and n states
✍ Yoshiyasu Ishigami; Sei'ichi Tani πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 723 KB

An investigation is conducted of the Vapnik-Chervonenkis dimensions (VC-dimensions) of finite automata having k letters and n states. It is shown for a fixed positive integer k ( > 2), that (1) the VC-dimension of DFAk(n) := {L c{1,2,...,k}\* : some deterministic finite automaton with at most n stat

Simulating finite automata with context-
Simulating finite automata with context-free grammars
✍ Michael Domaratzki; Giovanni Pighizzini; Jeffrey Shallit πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 78 KB

We consider simulating finite automata (both deterministic and nondeterministic) with context-free grammars in Chomsky normal form (CNF). We show that any unary DFA with n states can be simulated by a CNF grammar with O(n 1/3 ) variables, and this bound is tight. We show that any unary NFA with n st