On Robustness for the Skolem and Positivity Problems

From LRDE

Revision as of 14:30, 7 July 2022 by Bot (talk | contribs) (Created page with "{{Publication | published = true | date = 2022-07-07 | authors = S Akshay, Hugo Bazille, Blaise Genest, Mihir Vahanwala | editors = Petra Berenbrink, Benjamin Monmege | title...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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} 2022, March 15-18, 2022,
		  Marseille, France (Virtual Conference)},
  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},
  volume	= {219},
  pages		= {5:1--5:20},
  publisher	= {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year		= {2022},
  url		= {https://doi.org/10.4230/LIPIcs.STACS.2022.5},
  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}
}