On Rational Recursive Sequences

2025-05-06 0 0 812.88KB 21 页 10玖币

侵权投诉

Lorenzo Clemente !

University of Warsaw, Poland

Maria Donten-Bury !

University of Warsaw, Poland

Filip Mazowiecki !

University of Warsaw, Poland

Michał Pilipczuk !

University of Warsaw, Poland

Abstract

We study the class of rational recursive sequences (ratrec) over the rational numbers. A ratrec

sequence is deﬁned via a system of sequences using mutually recursive equations of depth 1, where

the next values are computed as rational functions of the previous values. An alternative class is

that of simple ratrec sequences, where one uses a single recursive equation, however of depth

: the

next value is deﬁned as a rational function of kprevious values.

We conjecture that the classes ratrec and simple ratrec coincide. The main contribution of this

paper is a proof of a variant of this conjecture where the initial conditions are treated symbolically,

using a formal variable per sequence, while the sequences themselves consist of rational functions

over those variables. While the initial conjecture does not follow from this variant, we hope that the

introduced algebraic techniques may eventually be helpful in resolving the problem.

The class ratrec strictly generalises a well-known class of polynomial recursive sequences (polyrec).

These are deﬁned like ratrec, but using polynomial functions instead of rational ones. One can

observe that if our conjecture is true and eﬀective, then we can improve the complexities of the

zeroness and the equivalence problems for polyrec sequences. Currently, the only known upper

bound is Ackermanian, which follows from results on polynomial automata. We complement this

observation by proving a PSPACE lower bound for both problems for polyrec. Our lower bound

construction also implies that the Skolem problem is PSPACE-hard for the polyrec class.

2012 ACM Subject Classiﬁcation Replace ccsdesc macro with valid one

Keywords and phrases

recursive sequences, polynomial automata, zeroness problem, equivalence

problem

Digital Object Identiﬁer 10.4230/LIPIcs.CVIT.2016.23

Funding

Lorenzo Clemente: partially supported by the ERC grant INFSYS, agreement no. 950398.

Maria Donten-Bury: partially supported by the National Science Center, Poland, project 2017/26/E/ST1/00231.

Filip Mazowiecki: partially supported by the ERC grant INFSYS, agreement no. 950398.

Michał Pilipczuk: partially supported by the ERC grant BOBR, agreement no. 948057.

Acknowledgements I want to thank . . .

©Lorenzo Clemente, Maria Donten-Bury, Filip Mazowiecki and Michał Pilipczuk;

licensed under Creative Commons License CC-BY 4.0

42nd Conference on Very Important Topics (CVIT 2016).

Editors: John Q. Open and Joan R. Access; Article No. 23; pp. 23:1–23:21

Leibniz International Proceedings in Informatics

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

arXiv:2210.01635v1 [cs.FL] 4 Oct 2022

23:2 On Rational Recursive Sequences

1 Introduction

The topic of this paper are recursively deﬁned sequences of rational numbers

NÑQ

. There

are two natural ways to deﬁne such sequences. In a simple recursion of depth

one ﬁxes

initial values and deﬁnes the next value as a function of the previous

values. This is how

the Fibonacci sequence is usually deﬁned (with

k“

2):

f0“

f1“

1, and

fn`2“fn`1`fn

In a mutual recursion of width

one deﬁnes a system of

sequences such that every sequence

has its initial value and the update function can access the immediately previous value of all

sequences, but no older value. For example, we can deﬁne

an“n2

with an extra sequence

bn“n

as follows:

a0“b0“

0and

an`1“an`

bn`

bn`1“bn`

1. Both styles allow to

deﬁne various classes of sequences depending on what operations are allowed in the equations,

and in general mutual recursion of width

can simulate simple recursion of depth

(by

adding suﬃciently many auxiliary sequences).

One of the most well-known classes of sequences is the class of linear recursive sequences,

which is obtained by allowing the update function to use addition and multiplication with

constants. These are usually deﬁned with a simple recursion, like in the Fibonacci example,

but in fact, as a consequence of the Cayley-Hamilton theorem, one obtains the same class

when using mutual recursion [

, Lemma 1.1]. In particular, all the example sequences

anand bnare linear recursive.

Another natural class of sequences are the polynomial recursive sequences (polyrec),

which are deﬁned with mutual recursion and updates from the ring of polynomial functions

Qrx1, . . . , xks

. An example sequence from this class is

cn“n

!, where one can use the already

deﬁned sequence

and deﬁne

c0“

1and

cn`1“cn¨ pbn`

. To see the polynomials

behind this deﬁnition, let

and

be variables corresponding to

and

, respectively.

The polynomial to deﬁne

bn`1

Pbpx, yq “ x`

1, and the polynomial to deﬁne

cn`1

Pcpx, yq “ ypx`

. The class of simple polynomial recursive sequences is obtained by using

polynomial updates and a simple recursion (instead of mutual recursion) and it is known to

be strictly included in the class of all polyrec sequences. In particular, the sequence

polyrec but not simple polyrec [12, Theorem 3.1].

The deﬁnition via mutual recursion appears in the area of control theory (under the name

implicit representation of the space of states), and, in computer science, in the context of

weighted automata over

. Such automata output a rational number for every word over a

ﬁnite alphabet Σ, and they are deﬁned by linear updates [

]. Linear recursive sequences

are thus equivalent to weighted automata with a 1-letter alphabet Σ

“ tau

[

]. Similarly,

polyrec sequences are equivalent to polynomial automata [

] (also known as cost-register

automata [1]) with a 1-letter alphabet [12].

We are interested in two classical decision problems for such automata. Equivalence:

Given two automata

and

do they output the same number for every word, and zeroness:

Does the input automaton

output 0for every word. These problems are well-known to

be eﬃciently equivalent to each other: Zeroness is clearly a special case of equivalence (just

take

to output zero for every word), and equivalence of

A,B

reduces to zeroness of the

diﬀerence automaton

A´B

with the expected semantics. Therefore, we will consider only

the zeroness problem. From the seminal work of Schützenberger on minimisation of weighted

automata it follows that the zeroness problem for weighted automata is in PTIME [

] (in

fact even in

NC2

[

]). For polynomial automata over a binary alphabet, zeroness is known

to be Ackermann-complete [

]. Using the connection between sequences and automata one

immediately obtains

NC2

and Ackermann upper bounds for the zeroness problem of linear

recursive sequences, resp., polyrec sequences.

L. Clemente, M. Donten-Bury, F. Mazowiecki and M. Pilipczuk 23:3

Let us take a closer look at the zeroness problem for recursive sequences, i.e., given a

sequence

is it the case that

un“

0for all

nPN

? The zeroness problem is a fundamental

problem for number sequences. It is a basic building block in computer algebra, e.g., in proving

identities involving recursively deﬁned sequences. It is also important from a theoretical point

of view as a yardstick of the well-behavedness of classes of number sequences, i.e., interesting

classes of sequences should at least have a decidable zeroness problem. The diﬃculty of solving

the zeroness problem in general depends on how the sequence is presented. If the sequence is

deﬁned with a simple recursion of depth

such as

un`k“fpun`k´1, . . . , unq

, then zeroness

trivially reduces to checking that the ﬁrst

values are 0and that the recursive update

is well-deﬁned and needs to output 0when the previous values are 0, i.e.,

,...,

q “

However, this simple reasoning is ﬂawed in the case of mutual recursion, because the auxiliary

sequences employed in the mutual recursion need not be zero. However, for linear recursive

sequences the zeroness problem is easily solved even in the case of mutual recursion, because

the reduction to simple recursion [

, Lemma 1.1] implies that

is zero if, and only if,

its ﬁrst

1values

a0“ ¨¨¨ “ ak

are zero. For polyrec sequences we cannot apply this

argument since mutual recursion cannot be simulated by simple recursion in the case of

polynomial updates.

Our results

In this paper we introduce the class of rational recursive sequences (ratrec).

This class is deﬁned with mutual recursion and updates from the ﬁeld of rational functions

Qpx1, . . . , xkq

. For example, the Catalan numbers

Cn`1“2p2n`1q

n`2Cn

can be deﬁned using

as an auxiliary sequence. Namely,

C0“

1and

Cn`1“2p2bn`1q

bn`2Cn

, where the rational

function used to deﬁne

Cn`1

Rpx, yq “ 2p2x`1q

x`2y

. By deﬁnition, the class of polyrec

sequences is included in the class of ratrec sequences, and in fact the inclusion is strict

as witnessed by the fact that the Catalan numbers

are not polynomialy recursive [

Corollary 4.1]. Moreover, ratrec sequences also include the well-known and wide-spread

P-recursive sequences

[

], which according to a 2005 estimate comprise at least 25% of the

OEIS archive [29].

A natural question is whether the class of ratrec sequences semantically collapes to the

class of simple rational recursive sequences obtained by adopting simple recursion. Unlike

in the case of polynomial updates, we conjecture that for rational updates we do have such

a collapse.

§Conjecture 1.

The class of rational recursive sequences coincides with the class of simple

rational recursive sequences.

To see the power of ratrec sequences recall that

cn“n

!is not a simple polyrec sequence.

However, when in the recursion we allow rational functions, then

can be deﬁned with a

simple recursion, namely: cn`2“pcn`1q2

cn`cn`1. Thus cnis simple ratrec.

We introduce a technique towards proving Conjecture 1, which comes from commutative

algebra. Instead of looking at the elements of a ratrec sequence as numbers in the ﬁeld

of rationals

, we symbolically view them as elements of the ﬁeld of rational functions

Qpx1, . . . , xkq

. More precisely, we assume that the sequences

Fp1q,...,Fpkq

are initialised

by setting

Fpiq

0“xi

for all

iP t

, . . . , ku

; then, a system of recursive equations governed by

rational functions deﬁnes further entries of the sequences. Thus, the recursive deﬁnition will

Sometimes P-recursive sequences are also called holonomic sequences, due to a connection with holonomic

generating functions.

CVIT 2016

23:4 On Rational Recursive Sequences

output elements in

Qpx1, . . . , xkq

rather than

. Intuitively, this corresponds to treating the

initial conditions of a system of ratrec sequences symbolically, rather than instantiating them

with actual rational values.

Informally speaking, we prove Conjecture 1for symbolic ratrec sequences, as explained

above. Here is a semi-formal statement of our main result, see Theorem 6for a formalization.

§Theorem 2.

The class of rational recursive sequences over

Qpx1, . . . , xkq

, with the system

initialised by Fpiq

0“xi, coincides with the class of simple rational recursive sequences.

The proof proceeds as follows. From the functions deﬁning the ratrec system we build a

sequence of ﬁeld extensions

QĎF0ĎF1ĎF2Ď. . . ĎQpx1, . . . , xkq

and translate the problem of belonging to the class of simple ratrec sequences to the question

of whether this sequence of ﬁeld extensions eventually stabilises. In order to estimate at

which level the stabilisation occurs we use certain results on basic algorithms for rational

function ﬁelds [

]. We believe that this technique could be extended to prove Conjecture 1,

but we also show an example why our current results are not strong enough.

Note that if Conjecture 1is moreover eﬃcient, it gives a simple algorithm to check

zeroness for polyrec. Indeed, since polyrec is a particular case of ratrec, then once a sequence

is expressed as a simple ratrec it suﬃces to check whether the ﬁrst elements of the sequence

are 0. This would improve the Ackermann upper bound inherited from polynomial automata

from [

]. This suggests that for polyrec sequences the natural object of study are rational

function ﬁelds, which are of more algebraic nature and could provide better complexity

bounds than the order-theoretic techniques based on sequences of polynomial ideals and

Hilbert’s ﬁnite basis theorem [4].

Our ﬁnal result is a complexity lower bound for the zeroness problem of polyrec sequences.

§Theorem 3. The zeroness problem for polynomial recursive sequences is PSPACE-hard.

As far as we know, prior to this work nothing was known about the complexity of zeroness

for polyrec sequences, except for the Ackermann upper bound following from polynomial

automata [4]. The lower bound is proved by reducing from the QBF validity problem.

Given Conjecture 1it seems natural to investigate the zeroness problem for ratrec

sequences. The issue is that it is not clear what would be the input for such a decision

problem. Recall that to deﬁne ratrec sequences we allow for rational functions in the recursion,

which means that we have to deal with division in order to compute the elements of the

sequences. Then either one would require that the input sequence comes with a promise

that all elements are well-deﬁned and no division by 0occurs; or one would need to verify

whether division by 0occurs in the input sequence. We ﬁnd the former solution unnatural,

and the latter is at least as hard as the so-called Skolem problem (c.f. below), which is not

known to be decidable even for linear recursive sequences.

Related work

The zeroness problem has been extensively studied. In the ﬁeld of automata

theory, we can mention applications to the equivalence problem of several classes of automata

and grammars, starting from weighted ﬁnite automata [

] and polynomial automata [

]

already mentioned above, and including context-free grammars [

], multiplicity equivalence

of ﬁnite automata [

] and multitape ﬁnite automata [

], unambiguous context-free

grammars [

, Theorem 5.5] (c.f. [

] for a PSPACE upper bound), polynomial grammars

L. Clemente, M. Donten-Bury, F. Mazowiecki and M. Pilipczuk 23:5

(which generalise polynomial automata) [

, Chapter 11], deterministic top-down tree-to-

string transducers [

], MSO transductions on unordered forests [

], MSO transductions

of bounded treewidth under a certain equivalence relation [

], Parikh automata [

], and

unambiguous register automata [

]. By replacing (pointwise) multiplication with convolution

in the deﬁnition of polyrec sequences we obtain the so-called convolution recursive sequences,

for which the zeroness problem can be solved in PSPACE [14, Theorem 4].

The zeroness problem of D-ﬁnite [

] and, more generally, D-algebraic power series [

]

is known to be decidable, but its computational complexity has not been investigated.

A natural problem related to the zeroness problem is the so-called Skolem problem, which

asks whether a given sequence

has a zero, i.e., whether for some

we have

an“

0. As a

corollary of the constructions used to prove Theorem 3, it follows that the Skolem problem

for polyrec sequences is PSPACE-hard. Only NP-hardness was formerly known, and already

for linear recursive sequences [

, Corollary 2.1]. Decidability of the Skolem problem for

linear recursive sequences is a long-standing open problem (c.f. the survey paper [

]). It is

interesting to notice that those lower bounds are obtained already on the ﬁxed ﬁeld with

two elements

, and are thus of a combinatorial rather than numerical nature. The

Skolem problem for weighted automata over

(that generalise linear recursive sequences) is

undecidable [27].

2 Preliminaries

By Nwe denote the set of nonnegative integers. We denote an arbitrary ﬁeld by F, and we

use 0and 1to denote the zero, resp., one elements thereof. Example ﬁelds of interest in

this paper are: rationals

; and the two-element ﬁeld

. A sequence over a domain

is a

function

u:NÑD

. The sequences considered in this work are over domains that have a

ﬁeld structure, like rationals

. We use bold-face letters as a short-hand for sequences, e.g.,

u“ xunynPN.

In this paper we work with multivariate polynomials and rational functions. The (com-

bined) degree of a monomial

xd1

1¨¨¨xdk

d1` ¨¨¨ ` dk

and the degree of a polynomial

PPQpx1, . . . , xkq

, written

deg P

, is the maximum degree of monomials appearing in it. A

rational function is a formal fraction of two polynomials, where the denominator is required to

be non-zero. The degree of a rational function is the maximum of the degrees of the numerator

and the denominator. Recall that for any ﬁeld

and a set of variables

x1, . . . , xn

, polynomials

over

x1, . . . , xn

form the ring

Frx1, . . . , xns

, while rational functions over

x1, . . . , xn

form the

ﬁeld Fpx1, . . . , xnq. We also write Frxsand Fpxq, where x“ px1, . . . , xnq.

The computational aspects of multivariate polynomials, in particular their representation

on input to algorithms, are explained in Appendix A, as they will be of no concern in

Sections 3and 4.

3 Rational recursive sequences

We start with the central deﬁnitions, which were already discussed in Section 1.

§Deﬁnition 4.

A sequence

up1q

over a ﬁeld

is rationally recursive (or ratrec for short)

of dimension

and degree

if there exist auxiliary sequences

up2q,...,upkq

over

and

rational functions

P1, . . . , PkPFpx1, . . . , xkq

of degree at most

such that for all

nPN

, we

CVIT 2016

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

OnRationalRecursiveSequencesLorenzoClemente!UniversityofWarsaw,PolandMariaDonten-Bury!UniversityofWarsaw,PolandFilipMazowiecki!UniversityofWarsaw,PolandMichaªPilipczuk!UniversityofWarsaw,PolandAbstractWestudytheclassofrationalrecursivesequences(ratrec)overtherationalnumbers.Aratrecsequenceisdenedvi...

展开>> 收起<<

On Rational Recursive Sequences.pdf

共21页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

On Rational Recursive Sequences

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: