City Research Online

Classes of languages generated by the Kleene star of a word

Daviaud, L. and Paperman, C. (2018). Classes of languages generated by the Kleene star of a word. Information and Computation, 262, pp. 90-109. doi: 10.1016/j.ic.2018.07.002

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: Article
Additional Information: © 2018 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Publisher Keywords: Automata theory, Regular languages, Profinite equations, Kleene star, Decidability
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Mathematics, Computer Science & Engineering > Computer Science
URI: http://openaccess.city.ac.uk/id/eprint/21287
[img]
Preview
Text - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (460kB) | Preview

Export

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login