Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConnection Matrices and the Definability of Graph Parameters
139
0
0.0
(
0
)
Added by
Tomer Kotek
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper we extend and prove in detail the Finite Rank Theorem for connection matrices of graph parameters definable in Monadic Second Order Logic with counting (CMSOL) from B. Godlin, T. Kotek and J.A. Makowsky (2008) and J.A. Makowsky (2009). We demonstrate its vast applicability in simplifying known and new non-definability results of graph properties and finding new non-definability results for graph parameters. We also prove a Feferman-Vaught Theorem for the logic CFOL, First Order Logic with the modular counting quantifiers.
rate research
Read More
Motivated by the quest for a logic for PTIME and recent insights that the descriptive complexity of problems from linear algebra is a crucial aspect of this problem, we study the solvability of linear equation systems over finite groups and rings from the viewpoint of logical (inter-)definability. All problems that we consider are decidable in polynomial time, but not expressible in fixed-point logic with counting. They also provide natural candidates for a separation of polynomial time from rank logics, which extend fixed-point logics by operators for determining the rank of definable matrices and which are sufficient for solvability problems over fields. Based on the structure theory of finite rings, we establish logical reductions among various solvability problems. Our results indicate that all solvability problems for linear equation systems that separate fixed-point logic with counting from PTIME can be reduced to solvability over commutative rings. Moreover, we prove closure properties for classes of queries that reduce to solvability over rings, which provides normal forms for logics extended with solvability operators. We conclude by studying the extent to which fixed-point logic with counting can express problems in linear algebra over finite commutative rings, generalising known results on the logical definability of linear-algebraic problems over finite fields.
We compare the capabilities of two approaches to approximating graph isomorphism using linear algebraic methods: the emph{invertible map tests} (introduced by Dawar and Holm) and proof systems with algebraic rules, namely emph{polynomial calculus}, emph{monomial calculus} and emph{Nullstellensatz calculus}. In the case of fields of characteristic zero, these variants are all essentially equivalent to the the Weisfeiler-Leman algorithms. In positive characteristic we show that the invertible map method can simulate the monomial calculus and identify a potential way to extend this to the monomial calculus.
We take a graph theoretic approach to the problem of finding generators for those prime ideals of $mathcal{O}_q(mathcal{M}_{m,n}(mathbb{K}))$ which are invariant under the torus action ($mathbb{K}^*)^{m+n}$. Launois cite{launois3} has shown that the generators consist of certain quantum minors of the matrix of canonical generators of $mathcal{O}_q(mathcal{M}_{m,n}(mathbb{K}))$ and in cite{launois2} gives an algorithm to find them. In this paper we modify a classic result of Lindstr{o}m cite{lind} and Gessel-Viennot~cite{gv} to show that a quantum minor is in the generating set for a particular ideal if and only if we can find a particular set of vertex-disjoint directed paths in an associated directed graph.
Riordan matrices are infinite lower triangular matrices determined by a pair of formal power series over the real or complex field. These matrices have been mainly studied as combinatorial objects with an emphasis placed on the algebraic or combinatorial structure. The present paper contributes to the linear algebraic discussion with an analysis of Riordan matrices by means of the interaction of the properties of formal power series with the linear algebra. Specifically, it is shown that if a Riordan matrix $A$ is an $ntimes n$ pseudo-involution then the singular values of $A$ must come in reciprocal pairs in $Sigma$ of a singular value decomposition $A=USigma V^T$. Moreover, we give a complete analysis of the existence and nonexistence of eigenvectors of Riordan matrices. As a result, we obtain a surprising partition of the group of Riordan matrices into three different types of eigenvectors. Finally, given a nonzero vector $v$, we investigate the algebraic structure of Riordan matrices $A$ that stabilize the vector $v$, i.e. $Av=v$.
In this paper we investigate the $lambda$ -calculus, a $lambda$-calculus enriched with resource control. Explicit control of resources is enabled by the presence of erasure and duplication operators, which correspond to thinning and con-traction rules in the type assignment system. We introduce directly the class of $lambda$ -terms and we provide a new treatment of substitution by its decompo-sition into atomic steps. We propose an intersection type assignment system for $lambda$ -calculus which makes a clear correspondence between three roles of variables and three kinds of intersection types. Finally, we provide the characterisation of strong normalisation in $lambda$ -calculus by means of an in-tersection type assignment system. This process uses typeability of normal forms, redex subject expansion and reducibility method.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
