A note on off-line machines with 'Brownian' input heads
type: Item
instance of: scholarly article
title: A note on off-line machines with 'Brownian' input heads
zbMATH Open document ID: 0553.03026
DOI: 10.1016/0166-218X(84)90091-X
author: Keijo Ruohonen
published in: Discrete Applied Mathematics
publication date: 1984-01-01T00:00:00Z
review text: The author introduces off-line Turing machines with read-only input tape, where the machines cannot control and observe the moves on the input tape. The input tape has a left endmarker and a different right endmarker. In case of an input system regular languages as \(a^*\), \(a^ t\), \(\{a_ 1,...,a_ n\},\) \(\{\emptyset,a_ 1,...,a^ n\}\) can be accepted only. For languages with 3 symbols moves can be observed by looking at \((cab)^ n\) words. This can be used to show that every rec. enumerable language can be accepted. For binary languages it is proved that these languages are regular. The proof is not constructive and based on a well-partial order generated by so called random input sequences. One has the feeling that these binary languages are quite simple. An example of a regular language is missing, which cannot be accepted by this kind of machines. Such a counter example is the language \(\{a^ ib^ ja^ rb^ s(ab)^ n| n\in N\}\) for some fixed i, j, r, s.
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 3880672
zbMATH Keywords: off-line Turing machines with read-only input tape
zbMATH Keywords: regular languages
zbMATH Keywords: binary languages
MaRDI profile type: Publication
cites work: On free monoids partially ordered by embedding
cites work: An Approach to a Unified Theory of Automata
cites work: The theory of well-quasi-ordering: a frequently discovered concept
description: scientific article; zbMATH DE number 3880672