Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata

Mikolaj Bojanczyk; Bartek Klin; Joshua Moerman

Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata

Mikolaj Bojanczyk
, Bartek Klin
, Joshua Moerman

Research output: Working paper / Preprint › Preprint

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.

Original language	English
Publisher	Cornell University - arXiv
Publication status	Published - Apr 2021
Externally published	Yes

Access to Document

https://arxiv.org/abs/2104.02438Licence: CC BY

Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata.
Bojanczyk, M., Klin, B. & Moerman, J., 7 Jul 2021, 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE, p. 1-13 13 p.
Research output: Chapter in Book/Report/Conference proceeding › Conference Article in proceeding › Academic › peer-review

Cite this

@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",

}

TY - UNPB

T1 - Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata

AU - Bojanczyk, Mikolaj

AU - Klin, Bartek

AU - Moerman, Joshua

N1 - 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.

PY - 2021/4

Y1 - 2021/4

N2 - 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.

AB - 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.

M3 - Preprint

BT - Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata

PB - Cornell University - arXiv

ER -

Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata

Abstract

Access to Document

Fingerprint

Research output

Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata.

Cite this