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 21 departments and schools

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

They say the two most important days of your life are the day you were born, and the day you find out why

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