2026-07-23T22:21:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19412 2024-03-06T11:03:59Z ddc:004 open_access

Weighted One-Deterministic-Counter Automata Mathew, Prince Penelle, Vincent Saivasan, Prakash Sreejith, A.V. One-counter automata Equivalence Weighted automata Reachability We introduce weighted one-deterministic-counter automata (odca). These are weighted one-counter automata (oca) with the property of counter-determinacy, meaning that all paths labelled by a given word starting from the initial configuration have the same counter-effect. Weighted odcas are a strict extension of weighted visibly ocas, which are weighted ocas where the input alphabet determines the actions on the counter. We present a novel problem called the co-VS (complement to a vector space) reachability problem for weighted odcas over fields, which seeks to determine if there exists a run from a given configuration of a weighted odca to another configuration whose weight vector lies outside a given vector space. We establish two significant properties of witnesses for co-VS reachability: they satisfy a pseudo-pumping lemma, and the lexicographically minimal witness has a special form. It follows that the co-VS reachability problem is in 𝖯. These reachability problems help us to show that the equivalence problem of weighted odcas over fields is in 𝖯 by adapting the equivalence proof of deterministic real-time ocas [Stanislav Böhm and Stefan Göller, 2011] by Böhm et al. This is a step towards resolving the open question of the equivalence problem of weighted ocas. Finally, we demonstrate that the regularity problem, the problem of checking whether an input weighted odca over a field is equivalent to some weighted automaton, is in 𝖯. We also consider boolean odcas and show that the equivalence problem for (non-deterministic) boolean odcas is in PSPACE, whereas it is undecidable for (non-deterministic) boolean ocas. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prince Mathew and Vincent Penelle and Prakash Saivasan and A.V. Sreejith 2023 Is Part Of LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2023.39 urn:nbn:de:0030-drops-194129 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.39 eng https://creativecommons.org/licenses/by/4.0/legalcode