On Strongest Algebraic Program Invariants
On Strongest Algebraic Program Invariants
复制标题
关于最强代数程序不变量
DOI：
10.1145/3614319
复制
发表时间：
2023
影响因子：
2.5
通讯作者：
Hrushovski E
中科院分区：
文献类型：
--
作者：
Hrushovski E
多项式程序是一个所有赋值都由多项式表达式给出的程序，并且所有分支都是不确定的（与条件相反）。给定这样的程序，代数不变量是由每个程序位置的程序变量上的多项式方程定义的。Müller-Olm和Seidl提出了一个问题，即是否可以计算给定多项式程序的最强代数不变量。在这篇文章中，我们表明，虽然最强的代数不变量是不可计算的一般情况下，它们可以计算在特殊情况下的仿射程序，即程序与唯一的线性分配。对于后者的结果，我们的主要工具是一个代数结果的独立利益：给定一个有限的集合的理性方阵的相同的维度，我们展示了如何计算Zebriki封闭的半群，他们产生。
A polynomial program is one in which all assignments are given by polynomial expressions and in which all branching is nondeterministic (as opposed to conditional). Given such a program, an algebraic invariant is one that is defined by polynomial equations over the program variables at each program location. Müller-Olm and Seidl have posed the question of whether one can compute the strongest algebraic invariant of a given polynomial program. In this article, we show that, while strongest algebraic invariants are not computable in general, they can be computed in the special case of affine programs, that is, programs with exclusively linear assignments. For the latter result, our main tool is an algebraic result of independent interest: Given a finite set of rational square matrices of the same dimension, we show how to compute the Zariski closure of the semigroup that they generate.
登录
查看更多内容
影响因子：
1.7
作者：
P. Koiran
通讯作者：
P. Koiran
有限生成矩阵群Zariski闭包的计算
DOI：
--
发表时间：
2021
期刊：
International Symposium on Symbolic and Algebraic Computation
影响因子：
--
作者：
Klara Nosan;Amaury Pouly;S. Schmitz;M. Shirmohammadi;J. Worrell
通讯作者：
J. Worrell
2 × 2 整数矩阵隶属问题的可判定性
DOI：
--
发表时间：
2016
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
I. Potapov;P. Semukhin
通讯作者：
P. Semukhin
Kannan-Lipton 轨道问题的完整半代数不变综合
影响因子：
0.5
作者：
Nathanaël Fijalkow;Pierre Ohlmann;Joël Ouaknine;Amaury Pouly;J. Worrell
通讯作者：
J. Worrell
Kannan-Lipton 轨道问题的半代数不变综合
DOI：
--
发表时间：
2017
期刊：
Symposium on Theoretical Aspects of Computer Science
影响因子：
--
作者：
Nathanaël Fijalkow;Pierre Ohlmann;Joël Ouaknine;Amaury Pouly;J. Worrell
通讯作者：
J. Worrell