Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Monodic Tree Kleene Algebra
verfasst von : Toshinori Takai, Hitoshi Furusawa
Erschienen in: Relations and Kleene Algebra in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We propose a quasi-equational sound axiomatization of regular tree languages, called monodic tree Kleene algebra. The algebra is weaker than Kleene algebra introduced by Kozen. We find a subclass of regular tree languages, for which monodic tree Kleene algebra is complete. While regular tree expressions may have two or more kinds of place holders, the subclass can be equipped with only one kind of them. Along the lines of the original proof by Kozen, we prove the completeness theorem based on determinization and minimization of tree automata represented by matrices on monodic tree Kleene algebra.