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

Mikolaj Bojanczyk; Bartek Klin; Joshua Moerman

doi:10.1109/LICS52264.2021.9470634

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

Mikolaj Bojanczyk, Bartek Klin, Joshua Moerman

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference Article in proceeding › Academic › peer-review

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
Title of host publication	2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Publisher	IEEE
Pages	1-13
Number of pages	13
ISBN (Electronic)	978-1-6654-4895-6
ISBN (Print)	978-1-6654-4896-3
DOIs	https://doi.org/10.1109/LICS52264.2021.9470634
Publication status	Published - 7 Jul 2021
Event	36th Annual ACM/IEEE Symposium on Logic in Computer Science - Online, Rome, Italy Duration: 29 Jun 2021 → 2 Jul 2021 Conference number: 36 https://easyconferences.eu/lics2021/

Symposium

Symposium	36th Annual ACM/IEEE Symposium on Logic in Computer Science
Abbreviated title	LICS 2021
Country/Territory	Italy
City	Rome
Period	29/06/21 → 2/07/21
Internet address	https://easyconferences.eu/lics2021/

Access to Document

10.1109/LICS52264.2021.9470634

https://dblp.org/db/conf/lics/lics2021.html#BojanczykKM21

1 Preprint

Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata
Bojanczyk, M., Klin, B. & Moerman, J., Apr 2021, Cornell University - arXiv.
Research output: Working paper / Preprint › Preprint › Academic

Open Access

Cite this

@inproceedings{22ebd6c5c6b04207b73090afcd7189a7,

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.; 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021 ; Conference date: 29-06-2021 Through 02-07-2021",

year = "2021",

month = jul,

day = "7",

doi = "10.1109/LICS52264.2021.9470634",

language = "English",

isbn = "978-1-6654-4896-3",

pages = "1--13",

booktitle = "2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)",

publisher = "IEEE",

address = "United States",

url = "https://easyconferences.eu/lics2021/",

}

TY - GEN

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

AU - Bojanczyk, Mikolaj

AU - Klin, Bartek

AU - Moerman, Joshua

N1 - Conference code: 36

PY - 2021/7/7

Y1 - 2021/7/7

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.

U2 - 10.1109/LICS52264.2021.9470634

DO - 10.1109/LICS52264.2021.9470634

M3 - Conference Article in proceeding

SN - 978-1-6654-4896-3

SP - 1

EP - 13

BT - 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)

PB - IEEE

T2 - 36th Annual ACM/IEEE Symposium on Logic in Computer Science

Y2 - 29 June 2021 through 2 July 2021

ER -

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

Abstract

Symposium

Access to Document

Fingerprint

Research output

Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata

Cite this