New Techniques for Universality in Unambiguous Register Automata
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10437944" target="_blank" >RIV/00216208:11320/21:10437944 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.ICALP.2021.129" target="_blank" >https://doi.org/10.4230/LIPIcs.ICALP.2021.129</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.ICALP.2021.129" target="_blank" >10.4230/LIPIcs.ICALP.2021.129</a>
Alternative languages
Result language
angličtina
Original language name
New Techniques for Universality in Unambiguous Register Automata
Original language description
Register automata are finite automata equipped with a finite set of registers ranging over the domain of some relational structure like (N; =) or (ℚ; <). Register automata process words over the domain, and along a run of the automaton, the registers can store data from the input word for later comparisons. It is long known that the universality problem, i.e., the problem to decide whether a given register automaton accepts all words over the domain, is undecidable. Recently, we proved the problem to be decidable in 2-ExpSpace if the register automaton under study is over (N; =) and unambiguous, i.e., every input word has at most one accepting run; this result was shortly after improved to 2-ExpTime by Barloy and Clemente. In this paper, we go one step further and prove that the problem is in ExpSpace, and in PSpace if the number of registers is fixed. Our proof is based on new techniques that additionally allow us to show that the problem is in PSpace for single-register automata over (ℚ;<). As a third technical contribution we prove that the problem is decidable (in ExpSpace) for a more expressive model of unambiguous register automata, where the registers can take values nondeterministically, if defined over (N; =) and only one register is used. (C) 2021 Wojciech Czerwiński, Antoine Mottet, and Karin Quaas.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
—
Continuities
R - Projekt Ramcoveho programu EK
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Leibniz International Proceedings in Informatics, LIPIcs
ISBN
978-3-95977-195-5
ISSN
1868-8969
e-ISSN
—
Number of pages
16
Pages from-to
1-16
Publisher name
Schloss Dagstuhl
Place of publication
Německo
Event location
Skotsko
Event date
Jul 12, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—