Do stringology, combinatorics on word, and automatic sequences cover the same topic?

Question

https://en.wikipedia.org/wiki/String_(computer_science)#String_processing_algorithms says

The name stringology was coined in 1984 by computer scientist Zvi Galil for the issue of algorithms and data structures used for string processing

https://en.wikipedia.org/wiki/Combinatorics_on_words says

Combinatorics on words is a fairly new field of mathematics, branching from combinatorics, which focuses on the study of words and formal languages.

https://en.wikipedia.org/wiki/Combinatorics_on_words#Language_hierarchy says

Possibly the most applied result in combinatorics on words is the Chomsky hierarchy,[verification needed] developed by Noam Chomsky. He studied formal language in the 1950s.[2] His way of looking at language simplified the subject. He disregards the actual meaning of the word, does not consider certain factors such as frequency and context, and applies patterns of short terms to all length terms. The basic idea of Chomsky's work is to divide language into four levels, or the language hierarchy. The four levels are: regular, context-free, context-sensitive, and computably enumerable or unrestricted.[2] Regular is the least complex while computably enumerable is the most complex. While his work grew out of combinatorics on words, it drastically affected other disciplines, especially computer science.[3]

Jean-Paul Allouche and Jeffrey Shallit's Automatic Sequences Theory, Applications, Generalizations says

The subject of this book is automatic sequences and their generalizations. Automatic sequences form a class of sequences somewhere between simple order and chaotic disorder. This class contains such celebrated sequences as the Thue–Morse sequence (see Chapters 1 and 6) and the Rudin–Shapiro sequence (see Chapter 3), which play important roles in many different areas of mathematics. Automatic sequences are generated by finite automata, one of the most basic models of computation.

Questions:

1. Do stringology, combinatorics on word, and automatic sequences mean the same topic? (I guess so). What is the differences between them? ("Combinatorics on words" seems a vague term to me to name a theory, "stringology" seems better but I still don't know what it covers mathematically, and "automatic sequences" could be too specific and there might be other sequences studied in either combinatorics on words or stringology?)

2. Since "Possibly the most applied result in combinatorics on words is the Chomsky hierarchy", I understand that combinatorics on words are applications of Chomsky hierarchy. Do stringology, combinatorics on word, and automatic sequences focus on some type of languages in Chomsky hierarchy?

3. Since "automatic sequences are generated by finite automata", are stringology, combinatorics on word, and automatic sequences all about finite automata, not about more general automata (such as those for CFL's, CSL's, and r.e.'s)?

Thanks.

• Mauro ALLEGRANZA: IMO, the context of the topics above is relevant. Chomsky's approach must be understood in the context of his general project of a science of human language, that produce Generative Grammar: in a nutshell the project aimed at "explaining" human language using only syntax rules. If so, we cam imagine to formalize them (using the formal tools above) and produce e.g. automated translation software. It seems that the project did not succeed.

Answer 1

Question 1. I agree with wikipedia for stringology. Stringology is a part of algorithmic research that deals with the processing of text. It has a specialized conference series since 1996.

Combinatorics on words focuses on the study of words and infinite words. The bible on the topic is Lothaire's book [2], complemented by the other books [3, 4] of the same author. You can see the contents of these three books on Berstel's home page. See also the book [5] for connections with number theory.

Automatic sequences can be viewed as an important subchapter of combinatorics on words. The reference book on the topic is [1].

[1] J.-P. Allouche, J. Shallit, Automatic sequences. Theory, Applications, Generalizations, Cam- bridge University Press (2003), 571 + xvi pages.

[2] M. Lothaire, Combinatorics on words. Corrected reprint of the 1983 original. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1997. xviii+238 pp. ISBN: 0-521-59924-5

[3] M. Lothaire, Algebraic combinatorics on words. Encyclopedia of Mathematics and its Applications, 90 Cambridge University Press, Cambridge, 2002. xiv+504 pp. ISBN: 0-521-81220-8

[4] M. Lothaire, Applied combinatorics on words. Encyclopedia of Mathematics and its Applications, 105, Cambridge University Press, Cambridge, 2005. xvi+610 pp. ISBN: 978-0-521-84802-2; 0-521-84802-4

[5] Combinatorics, automata and number theory. Edited by Valérie Berthé and Michel Rigo. Encyclopedia of Mathematics and its Applications, 135. Cambridge University Press, Cambridge, 2010. xx+615 pp. ISBN: 978-0-521-51597-9

Question 2. No, combinatorics on words are not applications of Chomsky hierarchy.

Question 3. No again.