2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2021, p.1-13
2021
Volltextzugriff (PDF)
Details
- Autor(en) / Beteiligte
- Titel
- Orbit-finite-dimensional vector spaces and weighted register automata
- Ist Teil von
- 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2021, p.1-13
- Ort / Verlag
- Piscataway, NJ, USA: IEEE Press
- Erscheinungsjahr
- 2021
- Quelle
- ACM Digital Library
- Beschreibungen/Notizen
- 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.
- Sprache
- Englisch
- Identifikatoren
- ISBN: 9781665448956, 1665448954DOI: 10.1109/LICS52264.2021.9470634Titel-ID: cdi_ieee_primary_9470634
- Format
- –
- Schlagworte
- Automata, Complexity theory, Computer science, Mathematics of computing, Mathematics of computing -- Mathematical analysis, Mathematics of computing -- Mathematical analysis -- Numerical analysis, Mathematics of computing -- Probability and statistics, Mathematics of computing -- Probability and statistics -- Probabilistic representations, Mathematics of computing -- Probability and statistics -- Probabilistic representations -- Decision diagrams, Orbits, Registers, Software and its engineering, Space vehicles, Theory of computation, Theory of computation -- Formal languages and automata theory, Theory of computation -- Models of computation, Theory of computation -- Randomness, geometry and discrete structures, Theory of computation -- Theory and algorithms for application domains, Theory of computation -- Theory and algorithms for application domains -- Machine learning theory, Theory of computation -- Theory and algorithms for application domains -- Machine learning theory -- Reinforcement learning, Theory of computation -- Theory and algorithms for application domains -- Machine learning theory -- Reinforcement learning -- Sequential decision making