On Robustness for the Skolem and Positivity Problems

Authors

S Akshay, Hugo Bazille, Blaise Genest, Mihir Vahanwala

Where

39th International Symposium on Theoretical Aspects of Computer Science STACS

Type

inproceedings

Publisher

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Projects

AA"AA" is not in the list (Vaucanson, Spot, URBI, Olena, APMC, Tiger, Climb, Speaker ID, Transformers, Bison, ...) of allowed values for the "Related project" property.

Date

2022-07-07

Abstract

The Skolem problem is a long-standing open problem in linear dynamical systems: can a linear recurrence sequence (LRS) ever reach 0 from a given initial configuration? Similarly, the positivity problem asks whether the LRS stays positive from an initial configuration. Deciding Skolem (or positivity) has been open for half a century: The best known decidability results are for LRS with special properties (e.g., low order recurrences). On the other hand, these problems are much easier for "uninitialized" variants, where the initial configuration is not fixed but can vary arbitrarily: checking if there is an initial configuration from which the LRS stays positive can be decided by polynomial time algorithms (Tiwari in 2004, Braverman in 2006).

Documents

• Paper

Bibtex (lrde.bib)

@InProceedings{	  akshay.22.stacs,
  author	= {S. Akshay and Hugo Bazille and Blaise Genest and Mihir
		  Vahanwala},
  editor	= {Petra Berenbrink and Benjamin Monmege},
  title		= {On Robustness for the {Skolem} and Positivity Problems},
  booktitle	= {39th International Symposium on Theoretical Aspects of
		  Computer Science {STACS}},
  abstract	= {The Skolem problem is a long-standing open problem in
		  linear dynamical systems: can a linear recurrence sequence
		  (LRS) ever reach 0 from a given initial configuration?
		  Similarly, the positivity problem asks whether the LRS
		  stays positive from an initial configuration. Deciding
		  Skolem (or positivity) has been open for half a century:
		  The best known decidability results are for LRS with
		  special properties (e.g., low order recurrences). On the
		  other hand, these problems are much easier for
		  "uninitialized" variants, where the initial configuration
		  is not fixed but can vary arbitrarily: checking if there is
		  an initial configuration from which the LRS stays positive
		  can be decided by polynomial time algorithms (Tiwari in
		  2004, Braverman in 2006).},
  series	= {LIPIcs},
  month		= mar,
  volume	= {219},
  pages		= {5:1--5:20},
  publisher	= {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year		= {2022},
  doi		= {10.4230/LIPIcs.STACS.2022.5},
  timestamp	= {Sat, 12 Mar 2022 15:06:27 +0100},
  biburl	= {https://dblp.org/rec/conf/stacs/0001BGV22.bib},
  bibsource	= {dblp computer science bibliography, https://dblp.org}
}