Computer Science – Logic in Computer Science
Scientific paper
2007-01-25
LMCS 3 (1:4) 2007
Computer Science
Logic in Computer Science
37 pages
Scientific paper
10.2168/LMCS-3(1:4)2007
The study of finite automata and regular languages is a privileged meeting point of algebra and logic. Since the work of Buchi, regular languages have been classified according to their descriptive complexity, i.e. the type of logical formalism required to define them. The algebraic point of view on automata is an essential complement of this classification: by providing alternative, algebraic characterizations for the classes, it often yields the only opportunity for the design of algorithms that decide expressibility in some logical fragment. We survey the existing results relating the expressibility of regular languages in logical fragments of MSO[S] with algebraic properties of their minimal automata. In particular, we show that many of the best known results in this area share the same underlying mechanics and rely on a very strong relation between logical substitutions and block-products of pseudovarieties of monoid. We also explain the impact of these connections on circuit complexity theory.
Tesson Pascal
Therien Denis
No associations
LandOfFree
Logic Meets Algebra: the Case of Regular Languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Logic Meets Algebra: the Case of Regular Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Logic Meets Algebra: the Case of Regular Languages will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-568186