Languages with membership determined by single letter factors

التفاصيل البيبلوغرافية
العنوان: Languages with membership determined by single letter factors
المؤلفون: Suhear Alwan, Peter M. Higgins
المصدر: Theoretical Computer Science. 680:15-24
بيانات النشر: Elsevier BV, 2017.
سنة النشر: 2017
مصطلحات موضوعية: Discrete mathematics, Nested word, General Computer Science, Syntactic monoid, Abstract family of languages, Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Cone (formal languages), Pumping lemma for regular languages, Theoretical Computer Science, Combinatorics, symbols.namesake, Regular language, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, symbols, 020201 artificial intelligence & image processing, Möbius strip, Computer Science::Formal Languages and Automata Theory, Word (computer architecture), Mathematics
الوصف: 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 Mobius strip for a special class of rational languages.
تدمد: 0304-3975
URL الوصول: https://explore.openaire.eu/search/publication?articleId=doi_________::d412dbe3f6e9ef1a3b64180da52a5f1c
https://doi.org/10.1016/j.tcs.2017.04.005
حقوق: OPEN
رقم الأكسشن: edsair.doi...........d412dbe3f6e9ef1a3b64180da52a5f1c
قاعدة البيانات: OpenAIRE