Return to search

Languages that require full scanning of words to determine membership

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, Also, we investigate a topology on the free monoid that arises in the course of our research.

Identiferoai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:635550
Date January 2014
CreatorsAlwan, Suhear Saady
PublisherUniversity of Essex
Source SetsEthos UK
Detected LanguageEnglish
TypeElectronic Thesis or Dissertation

Page generated in 0.0025 seconds