STRICT LOCAL TESTABILITY OF THE FINITE CONTROL OF TWO-WAY AUTOMATA AND OF REGULAR PICTURE DESCRIPTION LANGUAGES

1 June 1991

journal article
Published by World Scientific Pub Co Pte Ltd in International Journal of Algebra and Computation

Vol. 1 (2) , 161-175
https://doi.org/10.1142/s0218196791000092

Abstract

We prove that every regular language is recognized by a deterministic two-way finite automaton whose control unit is strictly locally testing. Similarly, every picture language which can be described by a regular language can actually be described by a strictly locally testable language; this strengthens a result of Friedhelra Hinz.

Keywords

AUTOMATON
LOCAL TESTABILITY
STRICT LOCAL
FINITE CONTROL
REGULAR LANGUAGE
STRICTLY LOCALLY

This publication has 0 references indexed in Scilit: