Conference item
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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Publisher copy:
- 10.1109/lics52264.2021.9470634
Authors
- Publisher:
- IEEE
- Host title:
- 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
- Pages:
- 1-13
- Publication date:
- 2021-07-02
- Event title:
- 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2021)
- Event location:
- Rome, Italy
- Event website:
- https://easyconferences.eu/lics2021/
- Event start date:
- 2021-06-29
- Event end date:
- 2021-07-02
- DOI:
- ISSN:
-
1043-6871
- EISBN:
- 9781665448956
- ISBN:
- 9781665448963
- Language:
-
English
- Keywords:
- Pubs id:
-
1569725
- UUID:
-
uuid_88669222-c192-42bd-a9ca-46ab11c1f7ff
- Local pid:
-
pubs:1569725
- Deposit date:
-
2026-01-29
- ARK identifier:
Terms of use
- Copyright holder:
- IEEE
- Copyright date:
- 2021
- Rights statement:
- © 2021 IEEE
- Notes:
- This paper was presented at the 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2021), 29th June - 2nd July 2021, Rome, Italy.
If you are the owner of this record, you can report an update to it here: Report update to this record