Skip to main content

Seminar by Dr. Reino Niskanen

  • Date 20 Nov 2018
  • Time 3.00 pm – 4.00 pm, HLT2
  • Category Seminar

On the reachability problem in low-dimensional polynomial maps

Abstract

In this talk, I will introduce nondeterministic polynomial maps and related reachability problems. Polynomial maps can be seen as generalization of Vector Addition Systems, where the register updates are not restricted to incrementing and decrementing the current value but can be defined by arbitrary polynomials. In the reachability problem for polynomial maps we are asked whether there exists a finite composition of polynomials such that the given initial register value is evaluated to zero.

We consider different parameters in polynomial maps and study their effect on the decidability status of the reachability problem. In particular, we will show that the reachability problem is undecidable for three-dimensional affine maps and is PSPACE-complete for one-dimensional polynomial maps. We also investigate the role of VAS-like updates of the form x=x+a for some integer a. Surprisingly, we see that if we exclude the updates of this form, the problem becomes decidable in any dimension.

Bio

Reino Niskanen is a postdoc working on formal verification of string-manipulating programs at University of Oxford. Prior to arriving to Oxford, he did his PhD at University of Liverpool, where he studied decidability and complexity of the reachability problems in different models.

Related topics

Explore Royal Holloway

Get help paying for your studies at Royal Holloway through a range of scholarships and bursaries.

There are lots of exciting ways to get involved at Royal Holloway. Discover new interests and enjoy existing ones.

Heading to university is exciting. Finding the right place to live will get you off to a good start.

Whether you need support with your health or practical advice on budgeting or finding part-time work, we can help.

Discover more about our academic departments and schools.

Find out why Royal Holloway is in the top 25% of UK universities for research rated ‘world-leading’ or ‘internationally excellent’.

Royal Holloway is a research intensive university and our academics collaborate across disciplines to achieve excellence.

Discover world-class research at Royal Holloway.

Discover more about who we are today, and our vision for the future.

Royal Holloway began as two pioneering colleges for the education of women in the 19th century, and their spirit lives on today.

We’ve played a role in thousands of careers, some of them particularly remarkable.

Find about our decision-making processes and the people who lead and manage Royal Holloway today.