Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDecidability of the Membership Problem for $2times 2$ integer matrices
154
0
0.0
(
0
)
Added by
Pavel Semukhin
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 $2times 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).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
