اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدDecidability of the Membership Problem for $2times 2$ integer matrices
154
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The main result of this paper is the decidability of the membership problem for $2times 2$ nonsingular integer matrices. Namely, we will construct the first algorithm that for any nonsingular $2times 2$ integer matrices $M_1,dots,M_n$ and $M$ decides whether $M$ belongs to the semigroup generated by ${M_1,dots,M_n}$. Our algorithm relies on a translation of the numerical problem on matrices into combinatorial problems on words. It also makes use of some algebraical properties of well-known subgroups of $mathrm{GL}(2,mathbb{Z})$ and various new techniques and constructions that help to limit an infinite number of possibilities by reducing them to the membership problem for regular languages.
قيم البحث
اقرأ أيضاً
In this paper we prove the decidability of the HD0L ultimate periodicity problem.
Recursive matrices are ubiquitous in combinatorics, which have been extensively studied. We focus on the study of the sums of $2times 2$ minors of certain recursive matrices, the alternating sums of their $2times 2$ minors, and the sums of their $2ti
mes 2$ permanents. We obtain some combinatorial identities related to these sums, which generalized the work of Sun and Ma in [{it Electron. J. Combin. 2014}] and [{it European J. Combin. 2014}]. With the help of the computer algebra package {tt HolonomicFunctions}, we further get some new identities involving Narayana polynomials.
We show that Boolean matrix multiplication, computed as a sum of products of column vectors with row vectors, is essentially the same as Warshalls algorithm for computing the transitive closure matrix of a graph from its adjacency matrix. Warshalls
algorithm can be generalized to Floyds algorithm for computing the distance matrix of a graph with weighted edges. We will generalize Boolean matrices in the same way, keeping matrix multiplication essentially equivalent to the Floyd-Warshall algorithm. This way, we get matrices over a semiring, which are similar to the so-called funny matrices. We discuss our implementation of operations on Boolean matrices and on their generalization, which make use of vector instructions.
A multi-relational graph maintains two or more relations over a vertex set. This article defines an algebra for traversing such graphs that is based on an $n$-ary relational algebra, a concatenative single-relational path algebra, and a tensor-based
multi-relational algebra. The presented algebra provides a monoid, automata, and formal language theoretic foundation for the construction of a multi-relational graph traversal engine.
We present a new algorithm, Fractional Decomposition Tree (FDT) for finding a feasible solution for an integer program (IP) where all variables are binary. FDT runs in polynomial time and is guaranteed to find a feasible integer solution provided the
integrality gap is bounded. The algorithm gives a construction for Carr and Vempalas theorem that any feasible solution to the IPs linear-programming relaxation, when scaled by the instance integrality gap, dominates a convex combination of feasible solutions. FDT is also a tool for studying the integrality gap of IP formulations. We demonstrate that with experiments studying the integrality gap of two problems: optimally augmenting a tree to a 2-edge-connected graph and finding a minimum-cost 2-edge-connected multi-subgraph (2EC). We also give a simplified algorithm, Dom2IP, that more quickly determines if an instance has an unbounded integrality gap. We show that FDTs speed and approximation quality compare well to that of feasibility pump on moderate-sized instances of the vertex cover problem. For a particular set of hard-to-decompose fractional 2EC solutions, FDT always gave a better integer solution than the best previous approximation algorithm (Christofides).
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
