Algebraic Language Theory with Effects

Lenke F, Milius S, Urbat H, Wißmann T

Publication Type: Conference contribution

Journal

LIPIcs : Leibniz International Proceedings in Informatics Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik

Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Book Volume: 334

Conference Proceedings Title: Leibniz International Proceedings in Informatics, LIPIcs

Event location: Aarhus, DNK

ISBN: 9783959773720

DOI: 10.4230/LIPIcs.ICALP.2025.165

Abstract

Regular languages - the languages accepted by deterministic finite automata - are known to be precisely the languages recognized by finite monoids. This characterization is the origin of algebraic language theory. In this paper, we generalize the correspondence between automata and monoids to automata with generic computational effects given by a monad, providing the foundations of an effectful algebraic language theory. We show that, under suitable conditions on the monad, a language is computable by an effectful automaton precisely when it is recognizable by (1) an effectful monoid morphism into an effect-free finite monoid, and (2) a monoid morphism into a monad-monoid bialgebra whose carrier is a finitely generated algebra for the monad, the former mode of recognition being conceptually completely new. Our prime application is a novel algebraic approach to languages computed by probabilistic finite automata. Additionally, we derive new algebraic characterizations for nondeterministic probabilistic finite automata and for weighted finite automata over unrestricted semirings, generalizing previous results on weighted algebraic recognition over commutative rings.

Authors with CRIS profile

Fabian Lenke Lehrstuhl für Informatik 8 (Theoretische Informatik) Stefan Milius Lehrstuhl für Informatik 8 (Theoretische Informatik) Henning Urbat Lehrstuhl für Informatik 8 (Theoretische Informatik) Thorsten Wißmann Lehrstuhl für Informatik 8 (Theoretische Informatik)

How to cite

APA:

Lenke, F., Milius, S., Urbat, H., & Wißmann, T. (2025). Algebraic Language Theory with Effects. In Keren Censor-Hillel, Fabrizio Grandoni, Joel Ouaknine, Gabriele Puppis (Eds.), Leibniz International Proceedings in Informatics, LIPIcs. Aarhus, DNK: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.

MLA:

Lenke, Fabian, et al. "Algebraic Language Theory with Effects." Proceedings of the 52nd EATCS International Colloquium on Automata, Languages, and Programming, ICALP 2025, Aarhus, DNK Ed. Keren Censor-Hillel, Fabrizio Grandoni, Joel Ouaknine, Gabriele Puppis, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2025.

BibTeX: Download