20.500.12556/DiRROS-29429 Pumping-like results for copyless cost register automata and polynomially ambiguous weighted automata In this work we consider two rich subclasses of weighted automata over fields: polynomially ambiguous weighted automata and copyless cost register automata. Primarily we are interested in understanding their expressiveness power. Over the field of rationals and 1-letter alphabets, it is known that the two classes coincide; they are equivalent to linear recurrence sequences (LRS) whose exponential bases are roots of rationals. We develop a tool we call Pumping Sequence Families, which, by exploiting the simple single-letter behaviour of the models, yields two pumping-like results over arbitrary fields with unrestricted alphabets, one for each class. As a corollary of these results, we present examples proving that the two classes become incomparable over the field of rationals with unrestricted alphabets. We complement the results by analysing the zeroness and equivalence problems. For weighted automata (even unrestricted) these problems are well understood: there are polynomial time, and even NC$^2$ algorithms. For copyless cost register automata we show that the two problems are PSpace-complete, where the difficulty is to show the lower bound. weighted automata cost register automata ambiguity linear recurrence sequences equivalence problem končni avtomati linearna rekurzivna zaporedja true false true Angleški jezik Slovenski jezik Neznano 2026-05-18 13:55:07 2026-05-18 13:55:07 2026-05-19 03:54:41 0000-00-00 00:00:00 2026 0 0 str. 67:1-67:21 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004:511 1868-8969 10.4230/LIPIcs.STACS.2026.67 278513155 278507011 LIPIcs.STACS.2026.67.pdf LIPIcs.STACS.2026.67.pdf 1 11736C788E7ADEBF29895D958388B00C 5f0a88be105d904d5594af4da8712cb7c719fe9a542cfd8344f072a0ae5163a4 6be8904e-52b0-11f1-8a5a-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=44125 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.67 0 d958e403-52b0-11f1-8a5a-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=44129 Inštitut za matematiko, fiziko in mehaniko 0 0 0