Enumerating fuzzy switching functions and free kleene algebras

✍ Scribed by Joel Berman; Masao Mukaidono

• Publisher: Elsevier Science
• Year: 1984
• Tongue: English
• Weight: 933 KB
• Volume: 10
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/0898-1221(84)90083-x

✦ Synopsis

We investigate the free Kleene algebra on n free generators, FK(n). This algebra is essentially the same as the set of n-variable fuzzy switching functions. The cardinality of FK(n) has been previously determined only for n = 1,2, and 3. We present a general method for enumeration problems of this kind. We show FK(4) has 160,297,985,276 elements. The final section contains new upper and lower bounds for the cardinality of FK(n). We also consider the number of regular functions and show that there are 11,197,129,615, and 430,904,428,717 such functions in 1, 2, 3, and 4 variables.