Regular languages definable by Lindström quantifiers
Dept. of Computer Science,
University of Szeged,
6701 Szeged, Hungary; firstname.lastname@example.org.
2 Dept. of Computer Science, Aalborg University, Fredrik Bajers Vej 7E, 9220 Aalborg, Denmark; email@example.com.
Accepted: August 2003
In our main result, we establish a formal connection between Lindström quantifiers with respect to regular languages and the double semidirect product of finite monoids with a distinguished set of generators. We use this correspondence to characterize the expressive power of Lindström quantifiers associated with a class of regular languages.
Mathematics Subject Classification: 20M35 / 68Q45 / 68Q60 / 68Q70
Key words: Regular language / logic / Lindström quantifier / expressive power / semidirect product.
© EDP Sciences, 2003