Decidability of membership problems for flat rational subsets of GL(2, Q) and singular matrices
Decidability of membership problems for flat rational subsets of GL(2, Q) and singular matrices
复制标题
GL(2, Q) 和奇异矩阵的平有理子集隶属问题的可判定性
DOI：
10.1145/3373207.3404038
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Diekert V
中科院分区：
文献类型：
--
作者：
Diekert V
这项工作涉及数值问题的矩阵的理性符号算法的话和有限自动机。利用精确代数算法和符号计算，证明了Q上2 × 2矩阵的新的可判定性结果.也就是说，我们引入了平坦有理集的概念：如果M是幺半群，N ≤ M是它的子幺半群，则M相对于N的平坦有理集是L0 g1 L1···gtLt形式的有限并，其中所有的Lis是Ngi ∈M的有理子集.我们给出了平坦有理集形成有效相对布尔代数的相当一般的充分条件.作为推论，我们得到了GL（2，Q）在GL（2，Z）上的平坦有理子集的布尔组合的空性问题是可判定的，并证明了GL（2，Z）在GL（2，Q）中的非平凡群扩张的二分法：如果G是f.g.群，使得GL（2，Z）<G≤ GL（2，Q），则G要么<$GL（2，Z）× Zk，其中某个k ≥ 1，要么G包含Baumslag-Solitar群BS（1，q）的扩张，其中q ≥ 2，具有无穷指数。结果表明，在第一种情况下，G的成员问题是可判定的，但G的有理子集的等式问题是不可判定的。在第二种情况下，可判定性的成员资格问题是开放的，为每一个suchG。在最后一节中，我们证明了新的可判定性的结果，平坦的有理集，包含奇异矩阵。特别地，我们证明了M（2，Q）的平坦有理子集相对于由行列式为0，± 1的矩阵fromM（2，Z）和中心有理矩阵生成的子幺半群的隶属问题是可判定的。
This work relates numerical problems on matrices over the rationals to symbolic algorithms on words and finite automata. Using exact algebraic algorithms and symbolic computation, we prove new decidability results for 2 × 2 matrices over Q. Namely, we introduce a notion offlat rational sets: ifMis a monoid andN≤Mis its submonoid, then flat rational sets ofMrelative toNare finite unions of the formL0g1L1···gtLtwhere allLis are rational subsets ofNandgi∈M.We give quite general sufficient conditions under which flat rational sets form an effective relative Boolean algebra. As a corollary, we obtain that the emptiness problem for Boolean combinations of flat rational subsets of GL(2, Q) over GL(2, Z) is decidable.We also show a dichotomy for nontrivial group extension of GL(2, Z) in GL(2, Q): ifGis a f.g. group such that GL(2, Z) <G≤ GL(2, Q), then eitherG≅ GL(2, Z) × Zk, for somek≥ 1, orGcontains an extension of the Baumslag-Solitar group BS(1,q), withq≥ 2, of infinite index. It turns out that in the first case the membership problem forGis decidable but the equality problem for rational subsets ofGis undecidable. In the second case, decidability of the membership problem is open for every suchG.In the last section we prove new decidability results for flat rational sets that contain singular matrices. In particular, we show that the membership problem is decidable for flat rational subsets ofM(2, Q) relative to the submonoid that is generated by the matrices fromM(2, Z) with determinants 0, ± 1 and the central rational matrices.
登录
查看更多内容
具有三个定义关系的群 PSL(2, p) 的呈现
DOI：
--
发表时间：
1969
期刊：
Canadian Journal of Mathematics - Journal Canadien de Mathematiques
影响因子：
--
作者：
H. Zassenhaus
通讯作者：
H. Zassenhaus
Flat FIFO 系统的验证
DOI：
--
发表时间：
2019
期刊：
International Conference on Concurrency Theory
影响因子：
--
作者：
A. Finkel;M. Praveen
通讯作者：
M. Praveen
有理跟踪语言的“最后”决策问题
DOI：
--
发表时间：
1992
期刊：
Latin American Symposium on Theoretical Informatics
影响因子：
--
作者：
J. Sakarovitch
通讯作者：
J. Sakarovitch
DOI：
10.2307/j.ctvc77m52.72
发表时间：
2019
期刊：
99 Variations on a Proof
影响因子：
--
作者：
Y. Lafont
通讯作者：
Y. Lafont
影响因子：
0.8
作者：
V. Diekert;M. Elder
通讯作者：
M. Elder