Classes of Languages Generated by the Kleene Star of a Word

Daviaud, L. & Paperman, C. (2015). Classes of Languages Generated by the Kleene Star of a Word. In: Italiano, G., Pughizzini, G. & Sannella, D. (Eds.), Mathematical Foundations of Computer Science 2015. MFCS 2015. Lecture Notes in Computer Science, 9234. (pp. 161-178). Berlin: Springer. ISBN 978-3-662-48056-4 doi: 10.1007/978-3-662-48057-1_13

Abstract

In this paper, we study the lattice and the Boolean algebra, possibly closed under quotient, generated by the languages of the form u∗, where u is a word. We provide effective equational characterisations of these classes, i.e. one can decide using our descriptions whether a given regular language belongs or not to each of them.

Publication Type:	Conference or Workshop Item (Paper)
Publisher Keywords:	Normal Form, Boolean Algebra, Regular Language, Finite Union, Finite Intersection
Departments:	School of Science & Technology > Computer Science