Languages That Require Full Scanning of Words to Determine Membership
Peter M. Higgins, Suhear Alwan · Open Access at Essex (University of Essex) · 2013
We introduce the full scan condition on a language, which captures the idea that the membership question for a word $w$ cannot be determined from a given prefix, suffix pair. We study the corresponding one-sided conditions, establish relationships between them, characterize these languages in the regular case through their minimal automata and syntactic monoids, and develop techniques for testing regularity of a language. Finally we investigate a topology on the free monoid that arises in the course of our research.