Research Repository

Languages with membership determined by single letter factors

Higgins, Peter M and Alwan, Suhear (2017) 'Languages with membership determined by single letter factors.' Theoretical Computer Science, 680. pp. 15-24. ISSN 0304-3975

Full text not available from this repository.


The full scan condition on a language L introduced in [1] ensures that a word w must be completely inspected in order to decide whether or not w lies in L. We strengthen the condition by replacing the factor words in that definition by single letters. After examining the general case for both arbitrary and regular languages, we investigate the two-letter alphabet to find a complete description of the corresponding languages, which may be coded as infinite binary strings. Regularity of these languages corresponds to the associated numbers being rational and we find the minimal automata in all cases, which may be pictured as a cylinder of tape with a protruding end, although this cylinder is replaced by a Möbius strip for a special class of rational languages.

Item Type: Article
Uncontrolled Keywords: Automata; Regular languages; Syntactic monoid; Word scanning
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science and Health
Faculty of Science and Health > Mathematical Sciences, Department of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 19 May 2017 09:36
Last Modified: 18 Aug 2022 11:23

Actions (login required)

View Item View Item