Morphisms and minimisation of weighted automata

• Autorzy: Lombardy Sylvain , Sakarovitch Jacques

Identyfikatory

DOI

10.3233/FI-222126

• Języki publikacji: EN

Abstrakty

EN

This paper studies the algorithms for the minimisation of weighted automata. It starts with the definition of morphisms-which generalises and unifies the notion of bisimulation to the whole class of weighted automata-and the unicity of a minimal quotient for every automaton, obtained by partition refinement. From a general scheme for the refinement of partitions, two strategies are considered for the computation of the minimal quotient: the Domain Split and the Predecesor Class Split algorithms. They correspond respectivly to the classical Moore and Hopcroft algorithms for the computation of the minimal quotient of deterministic Boolean automata. We show that these two strategies yield algorithms with the same quadratic complexity and we study the cases when the second one can be improved in order to achieve a complexity similar to the one of Hopcroft algorithm.

Słowa kluczowe

EN

Computer Science - Discrete Mathematics; Computer Science - Formal Languages and Automata Theory Licence

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 186, nr 1-4
• Strony: 195--218
• Opis fizyczny: Bibliogr. 31 poz., rys., tab.

Twórcy

autor

Lombardy Sylvain

• LaBRI - UMR 5800 - Bordeaux INP - Bordeaux University - CNRS Bordeaux, France

autor

Sakarovitch Jacques

• IRIF - CNRS/Paris Cit´e University and Telecom Paris, IPP Paris

Bibliografia

• [1] Hopcroft JE, Motwani R, Ullman JD. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 2006. 3rd edition. ISBN-10:0321455363, 13:978-0321455369.
• [2] Pin J ´E (ed.). Handbook of Automata Theory. EMS Press, 2021. ISBN-978-3-98547-006-8.
• [3] Berstel J, Boasson L, Carton O, Fagnot I. Minimisation of Automata. In: Pin J ´E (ed.), Handbook of Automata Theory, Vol. I, pp. 337-373. EMS Press, 2021. doi:10.48550/arXiv.2008.06790.
• [4] Droste M, Kuich W, Vogler H (eds.). Handbook of Weighted Automata. Springer, 2009. doi:10.1007/978-3-642-01492-5.
• [5] Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Freeman, 1979. ISBN-10:0716710455, 13:978-0716710455.
• [6] Baier C, Hermanns H. Weak Bisimulation for Fully Probabilistic Processes. In: Grumberg O (ed.), CAV 1997, volume 1254 of Lect. Notes in Comput. Sci. Springer, 1997 pp. 119-130. doi:10.1007/3-540-63166-614.
• [7] Boreale M. Weighted Bisimulation in Linear Algebraic Form. In: Bravetti M, Zavattaro G (eds.), CON-CUR 2009, volume 5710 of Lect. Notes in Comput. Sci. Springer, 2009 pp. 163-177. doi:10.1007/978-3-642-04081-8 12.
• [8] AWALI: Another Weighted Automata LIbrary. vaucanson-project.org/Awali.
• [9] Lombardy S, Sakarovitch J. Two Routes to Automata Minimization and the Ways to Reach It Efficiently. In: Cˆampeanu C (ed.), CIAA 2018, volume 10977 of Lect. Notes in Comput. Sci. Springer, 2018 pp. 248-260. doi:10.1007/978-3-319-94812-621.
• [10] Sakarovitch J. Elements of Automata Theory. Cambridge University Press, 2009. doi:10.1017/CBO9781139195218.
• [11] Frougny C, Sakarovitch J. Synchronized relations of finite and infinite words. Theoretical Computer Science, 1993. 108:45-82.
• [12] Reutenauer C. Subsequential functions: characterizations, minimization, examples. In: IMYCS’90, number 464 in Lect. Notes in Comput. Sci. 1990 pp. 62-79.
• [13] Beal MP, Lombardy S, Sakarovitch J. Conjugacy and Equivalence of Weighted Automata and Functional Transducers. In: Grigoriev D (ed.), CSR 2006, number 3967 in Lect. Notes in Comput. Sci. 2006 pp. 58-69. doi:10.1007/117537289.
• [14] Lind D, Marcus B. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, 1995. doi:10.1017/CBO9780511626302.
• [15] Milner R. A Complete Axiomatisation for Observational Congruence of Finite-State Behaviors. Inf. Comput., 1989. 81(2):227-247.
• [16] Benson DB, Ben-Shachar O. Bisimulation of Automata. Inf. Comput., 1988. 79(1):60-83.
• [17] Larsen KG, Skou A. Bisimulation through Probabilistic Testing. Inf. Comput., 1991. 94(1):1-28. doi: 10.1016/0890-5401(91)90030-6.
• [18] Lombardy S, Sakarovitch J. Derived terms without derivation. J. Comput. Sci. and Cybernetics, 2021. 37(3):201-221. In arXiv: arxiv.org/abs/2110.09181.
• [19] Béal MP, Crochemore M. Minimizing incomplete automata. In: Finite-State Methods and Natural Language Processing FSMNLP’08. 2008 pp. 9-16. ISBN-9781586039752.
• [20] Moore EF. Gedanken-Experiments on Sequential Machines. In: Shannon C, McCarthy J (eds.), Automata Studies, pp. 129-153. Princeton University Press, 1956. doi:10.1515/9781400882618-006.
• [21] Paige R. Efficient Translation of External Input in a Dynamically Typed Language. In: Technology and Foundations - Information Processing IFIP’94, volume A-51 of IFIP Transactions. North-Holland, 1994 pp. 603-608. ID:9443428.
• [22] Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. ISBN-978-0-262-03384-8. URL http://mitpress.mit.edu/books/introduction-algorithms.
• [23] Knuth DE. The Art of Computer Programming, Volume III, Sorting and Searching, 2nd Edition. Addison-Wesley, 1998. ISBN-0201896850. URL https://www.worldcat.org/oclc/312994415.
• [24] JavaTM Platform. Standard Edition 17 API Specification. Class LinkedHashMap<K,V>, 2021. Available at: https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/LinkedHashMap.html.
• [25] Gries D. Describing an algorithm by Hopcroft. Acta Informatica, 1973. 2:97-109. doi:10.1007/BF00264025.
• [26] Berstel J, Carton O. On the Complexity of Hopcroft’s State Minimization Algorithm. In: Implementation and Application of Automata CIAA’04, volume 3317 of Lect. Notes in Comput. Sci. Springer, 2004 pp 35-44. doi:10.1007/978-3-540-30500-24.
• [27] Valmari A, Lehtinen P. Efficient Minimization of DFAs with Partial Transition. In: STACS’08, volume 1 of LIPIcs. Schloss Dagstuhl, 2008 pp. 645-656. doi:10.4230/LIPIcs.STACS.2008.1328.
• [28] Hopcroft JE. An n log n Algorithm for Minimizing States in a Finite Automaton. In: Kohavi Z, Paz A (eds.), Theory of Machines and Computations, pp. 189-196. Academic Press, New York, 1971. doi:10.1016/B978-0-12-417750-5.50022-1.
• [29] Paige R, Tarjan RE. Three Partition Refinement Algorithms. SIAM J. Comput., 1987. 16(6):973-989. doi:10.1137/0216062.
• [30] Fernandez JC. An Implementation of an Efficient Algorithm for Bisimulation Equivalence. Sci. Comput. Program., 1989. 13(1):219-236. doi:10.1016/0167-6423(90)90071-K.
• [31] Castiglione G, Restivo A, Sciortino M. On extremal cases of Hopcroft’s algorithm. Theor. Comput. Sci., 2010. 411(38-39):3414-3422. doi:10.1016/j.tcs.2010.05.025.