2026-07-23T00:26:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9588 2024-03-06T10:44:28Z ddc:004 open_access

On Hadamard Series and Rotating Q-Automata Dando, Louis-Marie Lombardy, Sylvain Rational series Hadamard operations Rotating automata Two-way automata In this paper, we study rotating Q-automata, which are (memoryless) automata with weights in Q, that can read the input tape from left to right several times. We show that the series realized by valid rotating Q-automata are Q-Hadamard series (which are the closure of Q-rational series by pointwise inverse), and that every Q-Hadamard series can be realized by such an automaton. We prove that, although validity of rotating Q-automata is undecidable, the equivalence problem is decidable on rotating Q-automata. Finally, we prove that every valid two-way Q-automaton admits an equivalent rotating Q-automaton. The conversion, which is effective, implies the decidability of equivalence of two-way Q-automata. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Louis-Marie Dando and Sylvain Lombardy 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.6 urn:nbn:de:0030-drops-95881 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.6 eng https://creativecommons.org/licenses/by/3.0/legalcode