کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950065 | 1440361 | 2016 | 24 صفحه PDF | دانلود رایگان |
Deterministic automata can be minimized by partition refinement (Moore's algorithm, Hopcroft's algorithm) or by reversal and determinization (Brzozowski's algorithm). In the coalgebraic perspective, the first approach can be phrased in terms of a minimization construction along the final sequence of a functor, whereas a crucial part of the second approach is based on a reachability construction along the initial sequence of another functor. We employ this coalgebraic perspective to establish a precise relationship between the two approaches to minimization, and show how they can be combined. Part of these results are extended to an approach for language equivalence of a general class of systems with branching, such as non-deterministic automata.
Journal: Electronic Notes in Theoretical Computer Science - Volume 325, 5 October 2016, Pages 253-276