文章基本信息

标题：A Quasiorder-Based Perspective on Residual Automata
本地全文：下载
作者：Pierre Ganty ; Elena Gutirrez ; Pedro Valero 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：170
页码：40:1-40:14
DOI：10.4230/LIPIcs.MFCS.2020.40
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Residual Automata; Quasiorders; Double-Reversal Method; Canonical RFA; Regular Languages