Open AccessRegular Languages Definable by Lindström Quantifiers (Preliminary Version)
Author(s) -
Zoltán Ésik,
Kim Guldstrand Larsen
Publication year - 2002
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v9i20.21950
Subject(s) - mathematics , regular language , semidirect product , connection (principal bundle) , generator (circuit theory) , expressive power , monoid , class (philosophy) , discrete mathematics , arithmetic , power (physics) , computer science , programming language , group (periodic table) , automaton , artificial intelligence , chemistry , physics , geometry , organic chemistry , quantum mechanics
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 monoid-generator pairs. We use this correspondence to characterize the expressive power of Lindström quantifiers associated with a class of regular languages. Superseded by BRICS-RS-03-28.