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...

書誌詳細
主要な著者:	Ko, SK, Niskanen, R, Potapov, I
フォーマット:	Conference item
出版事項:	Springer, Cham 2018

類似資料

Solving nondeterministic polynomial complete problems optically and the design of its light source
著者:: Zheng, Mengying.
出版事項: (2013)

Vector reachability problem in SL (2, ℤ)
著者:: Potapov, I, 等
出版事項: (2016)

Vector and scalar reachability problems in SL(2, Z)
著者:: Potapov, I, 等
出版事項: (2018)

Synthesis of Bounded Integer Parameters for Parametric Timed Reachability Games
著者:: Jovanović, A, 等
出版事項: (2013)

NONDETERMINISTIC DECISION RULES
著者:: Piotr Paszek
出版事項: (2015-04-01)

NONDETERMINISTIC DECISION RULES
著者:: Piotr Paszek
出版事項: (2015-04-01)

NONDETERMINISTIC DECISION RULES
著者:: Piotr Paszek
出版事項: (2015-04-01)

NONDETERMINISTIC DECISION RULES
著者:: Piotr Paszek
出版事項: (2015-04-01)

NONDETERMINISTIC DECISION RULES
著者:: Piotr Paszek
出版事項: (2015-01-01)

NONDETERMINISTIC DECISION RULES
著者:: Piotr Paszek
出版事項: (2015-04-01)

NONDETERMINISTIC DECISION RULES
著者:: Piotr Paszek
出版事項: (2015-04-01)

NONDETERMINISTIC DECISION RULES
著者:: Piotr Paszek
出版事項: (2015-04-01)

On polynomial pairs of integers
著者:: Ezerman, Martianus Frederic, 等
出版事項: (2015)

On affine reachability problems
著者:: Jaax, S, 等
出版事項: (2020)

A polynomial-time algorithm for reachability in branching VASS in dimension one
著者:: Göller, S, 等
出版事項: (2016)

A Nondeterministic Minimization Algorithm
著者:: Caprile, Bruno, 等
出版事項: (2004)

Bicategorical semantics for nondeterministic computation
著者:: Vicary, J, 等
出版事項: (2013)

A Creative Nondeterministic Computability
著者:: A M Anisov
出版事項: (2009-09-01)

Quantum integer-valued polynomials
著者:: Harman, Nathan Reid, 等
出版事項: (2017)

Reachability analysis of neural feedback loops using sparse polynomial optimisation
著者:: Newton, M, 等
出版事項: (2022)

Nondeterministic Time and Space Complexity Classes
著者:: Seiferas, Joel Irvin
出版事項: (2023)

Quantum and classical structures in nondeterministic computation
著者:: Pavlovic, D
出版事項: (2009)

Behavioural Pseudometrics for Nondeterministic Probabilistic Systems
著者:: Wenjie Du, 等
出版事項: (2022-12-01)

Residuality and Learning for Nondeterministic Nominal Automata
著者:: Joshua Moerman, 等
出版事項: (2022-02-01)

Simplifying Nondeterministic Finite Cover Automata
著者:: Cezar Câmpeanu
出版事項: (2014-05-01)

D2-SYNCHRONIZATION IN NONDETERMINISTIC AUTOMATA
著者:: Hanan Shabana
出版事項: (2018-12-01)

Deriving checking sequences for nondeterministic FSMs
著者:: Anton Ermakov
出版事項: (2018-10-01)

Nondeterministic State Complexity of Positional Addition
著者:: Galina Jirásková, 等
出版事項: (2009-07-01)

Decidability of the membership problem for 2 x 2 integer matrices
著者:: Potapov, I, 等
出版事項: (2017)

Uniform approximation by polynomials with integer coefficients
著者:: Artur Lipnicki
出版事項: (2016-01-01)

On the complexity of integer polynomial recursive sequences
著者:: S.S. Marchenkov
出版事項: (2022-10-01)

Cycles of polynomial mappings in two variables over rings of integers in quadratic fields
著者:: Pezda T.
出版事項: (2004-04-01)

Reachability problems for linear dynamical systems
著者:: Chonev, V
出版事項: (2015)

On complexity of veri¯cation of nondeterministic probabilistic multiagent systems
著者:: M. K. Valiev, 等
出版事項: (2010-12-01)

Algorithmic search for integer Abelian roots of a polynomial with integer Abelian coefficients
著者:: Tsybulya, Liliya Mikhailovna
出版事項: (2024-05-01)

Convex language semantics for nondeterministic probabilistic automata
著者:: Van Heerdt, G, 等
出版事項: (2018)

On refinement-closed security properties and nondeterministic compositions
著者:: Murray, T, 等
出版事項: (2009)

Optimal decentralized control of finite nondeterministic systems
出版事項: (2003)

Abstraction of nondeterministic situation calculus action theories
著者:: Banihashemi, B, 等
出版事項: (2023)

Fault tolerant quantum computation with nondeterministic gates.
著者:: Li, Y, 等
出版事項: (2010)