A Kleene theorem for free many-sorted algebras
2026-06-29 • Logic in Computer Science
Logic in Computer ScienceFormal Languages and Automata Theory
AI summaryⓘ
The authors expanded Kleene's theorem, which originally applied to simple algebraic systems with one type of element, to more complex systems that have many different types of elements. They showed that for these multi-typed systems, a language (a set of expressions) can be recognized by a machine if and only if it follows certain regular patterns. Their work depends on some technical conditions being met. This generalization helps connect concepts of language recognition and regularity in a broader algebraic setting.
Kleene's theoremfree algebramany-sorted algebrarecognizable languageregular languagefinitary assumptionsalgebraic structuresformal languagesmachine recognition
Authors
Lü Gong, Raúl Ruiz Mora, Nofre Sanmartín Vich, Enric Cosme Llópez
Abstract
In this work, we generalize Kleene's theorem from free single-sorted algebras to free many-sorted algebras. Our main result establishes that, under appropriate finitary assumptions, a language of a given sort in a free many-sorted algebra is recognizable if and only if it is regular.