@techreport{2d1903f5071c4b56b12228ac6ba037d0,
title = "Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata",
abstract = "We develop a theory of vector spaces spanned by orbit-finite sets. Using this theory, we give a decision procedure for equivalence of weighted register automata, which are the common generalization of weighted automata and register automata for infinite alphabets. The algorithm runs in exponential time, and in polynomial time for a fixed number of registers. As a special case, we can decide, with the same complexity, language equivalence for unambiguous register automata, which improves previous results in three ways: (a) we allow for order comparisons on atoms, and not just equality; (b) the complexity is exponentially better; and (c) we allow automata with guessing. ",
author = "Mikolaj Bojanczyk and Bartek Klin and Joshua Moerman",
note = "DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",
year = "2021",
month = apr,
language = "English",
publisher = "Cornell University - arXiv",
address = "United States",
type = "WorkingPaper",
institution = "Cornell University - arXiv",
}