文章基本信息

标题：Automata Minimization: a Functorial Approach
本地全文：下载
作者：Petrişan, Daniela ; Colcombet, Thomas
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2020
卷号：16
期号：1
页码：1-28
语种：English
出版社：Technical University of Braunschweig
摘要：In this paper we regard languages and their acceptors - such as deterministicor weighted automata, transducers, or monoids - as functors from inputcategories that specify the type of the languages and of the machines tocategories that specify the type of outputs. Our results are as follows: A) We provide sufficient conditions on the output category so thatminimization of the corresponding automata is guaranteed. B) We show how to lift adjunctions between the categories for output valuesto adjunctions between categories of automata. C) We show how this framework can be instantiated to unify several phenomenain automata theory, starting with determinization, minimization and syntacticalgebras. We provide explanations of Choffrut's minimization algorithm forsubsequential transducers and of Brzozowski's minimization algorithm in thissetting.
关键词：Computer Science - Logic in Computer Science;Computer Science - Formal Languages and Automata Theory