2026-07-22T11:53:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12707 2024-03-06T10:50:38Z ddc:004 open_access

A Quasiorder-Based Perspective on Residual Automata Ganty, Pierre Gutiérrez, Elena Valero, Pedro Residual Automata Quasiorders Double-Reversal Method Canonical RFA Regular Languages In this work, we define a framework of automata constructions based on quasiorders over words to provide new insights on the class of residual automata. We present a new residualization operation and a generalized double-reversal method for building the canonical residual automaton for a given language. Finally, we use our framework to offer a quasiorder-based perspective on NL^*, an online learning algorithm for residual automata. We conclude that quasiorders are fundamental to residual automata as congruences are to deterministic automata. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pierre Ganty and Elena Gutiérrez and Pedro Valero 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.40 urn:nbn:de:0030-drops-127071 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.40 eng https://creativecommons.org/licenses/by/3.0/legalcode