Star-Free Open Languages and Aperiodic Loops

Autor:	François Lemieux, Martin Beaudry, Denis Thérien
Rok vydání:	2007
Předmět:	Discrete mathematics Pure mathematics Closure (mathematics) Regular language Aperiodic graph Wreath product Group (mathematics) Context-free language Cone (formal languages) Pumping lemma for regular languages Mathematics
Zdroj:	STACS 2001 ISBN: 9783540416951 STACS
DOI:	10.1007/3-540-44693-1_8
Popis:	It is known that recognition of regular languages by finite monoids can be generalized to context-free languages and finite groupoids, which are finite sets closed under a binary operation. A loop is a groupoid with a neutral element and in which each element has a left and a right inverse. It has been shown that finite loops recognize exactly those regular languages that are open in the group topology. In this paper, we study the class of aperiodic loops, which are those loops that contain no nontrivial group. We show that this class is stable under various definitions, and we prove some closure properties. We also prove that aperiodic loops recognize only star-free open languages and give some examples. Finally, we show that the wreath product principle can be applied to groupoids, and we use it to prove a decomposition theorem for recognizers of regular open languages.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::43c8fe5413c2d0e168e23485d0c0da90 https://doi.org/10.1007/3-540-44693-1_8 Zobrazit plný text záznamu