Open AccessRegular Languages Definable by Lindström Quantifiers
Author(s) -
Zoltán Ésik,
Kim Guldstrand Larsen
Publication year - 2003
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v10i28.21796
Subject(s) - semidirect product , mathematics , expressive power , regular language , connection (principal bundle) , class (philosophy) , discrete mathematics , arithmetic , computer science , programming language , group (periodic table) , theoretical computer science , artificial intelligence , automaton , chemistry , geometry , organic chemistry
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.