Languages and formations generated by D4 and Q8

We describe the two classes of languages recognized by the groups D4 and Q8, respectively. Then we show that the formations of languages generated by these two classes are the same. We also prove that these two formations are closed under inverses of morphisms, which yields a language theoretic proo...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2019-12, Vol.800, p.155-172
Main Authors: Pin, Jean-Éric, Soler-Escrivà, Xaro
Format: Article
Language:English
Subjects:
Computer Science
Dihedral group
Formal Languages and Automata Theory
Group formation
Group Theory
Mathematics
Quaternion group
Regular languages
Variety of monoids
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We describe the two classes of languages recognized by the groups D4 and Q8, respectively. Then we show that the formations of languages generated by these two classes are the same. We also prove that these two formations are closed under inverses of morphisms, which yields a language theoretic proof of the fact that the group formations generated by D4 and Q8, respectively, are two equal varieties.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2019.10.023