Normal Forms for Elements of the* -continuous Kleene Algebras K⊗RC2′

Hopkins, Mark und Leiß, Hans (2023): Normal Forms for Elements of the* -continuous Kleene Algebras K⊗RC2′. 20th International Conference on Relational and Algebraic Methods in Computer Science (RAMiCS), Technologiezentrum Augsburg, Augsburg, GERMANY, April 03-06, 2023. Roland, Glück; Luigi, Santocanale und Michael, Winter (Hrsg.): In: Relational and Algebraic Methods in Computer Science : 20th International Conference, RAMiCS 2023, Augsburg, Germany, April 3–6, 2023, Proceedings, Bd. 13896 Cham, Switzerland: Springer. S. 122-139

Abstract

The tensor product K⊗R⁡C2′ of the ∗-continuous Kleene algebra K with the polycyclic ∗-continuous Kleene algebra C2′ over two bracket pairs contains a copy of the fixed-point closure of K: the centralizer of C2′ in K⊗R⁡C2′. As a next step, establishing a calculus for context-free expressions, we prove a representation of elements of K⊗R⁡C2′ by automata à la Kleene and refine it by normal form theorems that restrict the occurrences of brackets on paths through the automata.

• Dokumententyp: Konferenzbeitrag (Paper)
• Fakultätsübergreifende Einrichtungen: Centrum für Informations- und Sprachverarbeitung (CIS)
• Themengebiete: 000 Informatik, Informationswissenschaft, allgemeine Werke > 004 Informatik
• ISBN: 978-3-031-28082-5; 978-3-031-28083-2
• Ort: Cham, Switzerland
• Sprache: Englisch