Algebraic recognizability of languages

Abstract. Recognizable languages of finite words are part of every com-puter science cursus, and they are routinely described as a cornerstone for applications and for theory. We would like to briefly explore why that is, and how this word-related notion extends to more complex models, such as those developed for modeling distributed or timed behaviors.>En rq ¬ ªn å lìgo... In the beginning was the Word... Recognizable languages of finite words are part of every computer science cursus, and they are routinely described as a cornerstone for applications and for theory. We would like to briefly explore why that is, and how this word-related notion extends to more complex models, such as those developed for modeling distributed or timed behaviors. The notion of recognizable languages is a familiar one, associated with classi-cal theorems by Kleene, Myhill, Nerode, Elgot, Büchi, Schützenberger, etc. It can be approached from several angles: recognizability by automata, recognizability by finite monoids or finite-index congruences, rational expressions, monadic sec