Reachability problems in nondeterministic polynomial maps on the integers

Reachability problems in nondeterministic polynomial maps on the integers

We study the reachability problems in various nondeterministic polynomial maps in Zn. We prove that the reachability problem for very simple three-dimensional affine maps (with independent variables) is undecidable and is PSPACE-hard for two-dimensional quadratic maps. Then we show that the complexi...

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Ko, SK, Niskanen, R, Potapov, I
Formáid:	Conference item
Foilsithe / Cruthaithe:	Springer, Cham 2018

Míreanna comhchosúla

Solving nondeterministic polynomial complete problems optically and the design of its light source
de réir: Zheng, Mengying.
Foilsithe / Cruthaithe: (2013)

Vector reachability problem in SL (2, ℤ)
de réir: Potapov, I, et al.
Foilsithe / Cruthaithe: (2016)

Vector and scalar reachability problems in SL(2, Z)
de réir: Potapov, I, et al.
Foilsithe / Cruthaithe: (2018)

Synthesis of Bounded Integer Parameters for Parametric Timed Reachability Games
de réir: Jovanović, A, et al.
Foilsithe / Cruthaithe: (2013)

NONDETERMINISTIC DECISION RULES
de réir: Piotr Paszek
Foilsithe / Cruthaithe: (2015-04-01)

NONDETERMINISTIC DECISION RULES
de réir: Piotr Paszek
Foilsithe / Cruthaithe: (2015-04-01)

NONDETERMINISTIC DECISION RULES
de réir: Piotr Paszek
Foilsithe / Cruthaithe: (2015-04-01)

NONDETERMINISTIC DECISION RULES
de réir: Piotr Paszek
Foilsithe / Cruthaithe: (2015-04-01)

NONDETERMINISTIC DECISION RULES
de réir: Piotr Paszek
Foilsithe / Cruthaithe: (2015-01-01)

NONDETERMINISTIC DECISION RULES
de réir: Piotr Paszek
Foilsithe / Cruthaithe: (2015-04-01)

NONDETERMINISTIC DECISION RULES
de réir: Piotr Paszek
Foilsithe / Cruthaithe: (2015-04-01)

NONDETERMINISTIC DECISION RULES
de réir: Piotr Paszek
Foilsithe / Cruthaithe: (2015-04-01)

On polynomial pairs of integers
de réir: Ezerman, Martianus Frederic, et al.
Foilsithe / Cruthaithe: (2015)

On affine reachability problems
de réir: Jaax, S, et al.
Foilsithe / Cruthaithe: (2020)

A polynomial-time algorithm for reachability in branching VASS in dimension one
de réir: Göller, S, et al.
Foilsithe / Cruthaithe: (2016)

A Nondeterministic Minimization Algorithm
de réir: Caprile, Bruno, et al.
Foilsithe / Cruthaithe: (2004)

Bicategorical semantics for nondeterministic computation
de réir: Vicary, J, et al.
Foilsithe / Cruthaithe: (2013)

A Creative Nondeterministic Computability
de réir: A M Anisov
Foilsithe / Cruthaithe: (2009-09-01)

Quantum integer-valued polynomials
de réir: Harman, Nathan Reid, et al.
Foilsithe / Cruthaithe: (2017)

Reachability analysis of neural feedback loops using sparse polynomial optimisation
de réir: Newton, M, et al.
Foilsithe / Cruthaithe: (2022)

Nondeterministic Time and Space Complexity Classes
de réir: Seiferas, Joel Irvin
Foilsithe / Cruthaithe: (2023)

Quantum and classical structures in nondeterministic computation
de réir: Pavlovic, D
Foilsithe / Cruthaithe: (2009)

Behavioural Pseudometrics for Nondeterministic Probabilistic Systems
de réir: Wenjie Du, et al.
Foilsithe / Cruthaithe: (2022-12-01)

Residuality and Learning for Nondeterministic Nominal Automata
de réir: Joshua Moerman, et al.
Foilsithe / Cruthaithe: (2022-02-01)

Simplifying Nondeterministic Finite Cover Automata
de réir: Cezar Câmpeanu
Foilsithe / Cruthaithe: (2014-05-01)

D2-SYNCHRONIZATION IN NONDETERMINISTIC AUTOMATA
de réir: Hanan Shabana
Foilsithe / Cruthaithe: (2018-12-01)

Deriving checking sequences for nondeterministic FSMs
de réir: Anton Ermakov
Foilsithe / Cruthaithe: (2018-10-01)

Nondeterministic State Complexity of Positional Addition
de réir: Galina Jirásková, et al.
Foilsithe / Cruthaithe: (2009-07-01)

Decidability of the membership problem for 2 x 2 integer matrices
de réir: Potapov, I, et al.
Foilsithe / Cruthaithe: (2017)

Uniform approximation by polynomials with integer coefficients
de réir: Artur Lipnicki
Foilsithe / Cruthaithe: (2016-01-01)

On the complexity of integer polynomial recursive sequences
de réir: S.S. Marchenkov
Foilsithe / Cruthaithe: (2022-10-01)

Cycles of polynomial mappings in two variables over rings of integers in quadratic fields
de réir: Pezda T.
Foilsithe / Cruthaithe: (2004-04-01)

Reachability problems for linear dynamical systems
de réir: Chonev, V
Foilsithe / Cruthaithe: (2015)

On complexity of veri¯cation of nondeterministic probabilistic multiagent systems
de réir: M. K. Valiev, et al.
Foilsithe / Cruthaithe: (2010-12-01)

Algorithmic search for integer Abelian roots of a polynomial with integer Abelian coefficients
de réir: Tsybulya, Liliya Mikhailovna
Foilsithe / Cruthaithe: (2024-05-01)

Convex language semantics for nondeterministic probabilistic automata
de réir: Van Heerdt, G, et al.
Foilsithe / Cruthaithe: (2018)

On refinement-closed security properties and nondeterministic compositions
de réir: Murray, T, et al.
Foilsithe / Cruthaithe: (2009)

Optimal decentralized control of finite nondeterministic systems
Foilsithe / Cruthaithe: (2003)

Abstraction of nondeterministic situation calculus action theories
de réir: Banihashemi, B, et al.
Foilsithe / Cruthaithe: (2023)

Fault tolerant quantum computation with nondeterministic gates.
de réir: Li, Y, et al.
Foilsithe / Cruthaithe: (2010)