English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the universality and inclusion problems for register automata overequality data. We show that the universality and the inclusion problems can besolved with 2-EXPTIME complexity when the input automata are without guessingand unambiguous, improving on the currently best-known 2-EXPSPACE upper boundby Mottet and Quaas. When the number of registers of both automata is fixed, weobtain a lower EXPTIME complexity, also improving the EXPSPACE upper bound fromMottet and Quaas for fixed number of registers. We reduce inclusion touniversality, and then we reduce universality to the problem of counting thenumber of orbits of runs of the automaton. We show that the orbit-countingfunction satisfies a system of bidimensional linear recursive equations withpolynomial coefficients (linrec), which generalises analogous recurrences forthe Stirling numbers of the second kind, and then we show that universalityreduces to the zeroness problem for linrec sequences. While such a countingapproach is classical and has successfully been applied to unambiguous finiteautomata and grammars over finite alphabets, its application to registerautomata over infinite alphabets is novel. We provide two algorithms to decidethe zeroness problem for bidimensional linear recursive sequences arising fromorbit-counting functions. Both algorithms rely on techniques from linearnon-commutative algebra. The first algorithm performs variable elimination andhas elementary complexity. The second algorithm is a refined version of thefirst one and it relies on the computation of the Hermite normal form ofmatrices over a skew polynomial field. The second algorithm yields an EXPTIMEdecision procedure for the zeroness problem of linrec sequences, which in turnyields the claimed bounds for the universality and inclusion problems ofregister automata.

Bidimensional linear recursive sequences and universality of unambiguous register automata