Chomsky and Schützenberger showed in 1963 that the sequence dL(n), which counts the number of words of a given length n in a regular language L, satisfies a linear recurrence relation with constant ...coefficients for n, i.e., it is C-finite. It follows that every sequence s(n) which satisfies a linear recurrence relation with constant coefficients can be represented as dL1(n)−dL2(n) for two regular languages. We view this as a representation theorem for C-finite sequences. Holonomic or P-recursive sequences are sequences which satisfy a linear recurrence relation with polynomial coefficients. q-Holonomic sequences are the q-analog of holonomic sequences. In this paper we prove representation theorems of holonomic and q-holonomic sequences based on position specific weights on words, and for holonomic sequences, without using weights, based on sparse regular languages.
•We prove representation theorems for sequences with recurrence relations.•(q-)Holonomic sequences are captured by appropriate logical interpretations.•Representations based on positional weights of words in regular languages are shown.•A weightless sparse-structures representation is given for holonomic sequences only.
A logician's view of graph polynomials Makowsky, J.A.; Ravve, E.V.; Kotek, T.
Annals of pure and applied logic,
September 2019, 2019-09-00, Letnik:
170, Številka:
9
Journal Article
Recenzirano
Odprti dostop
Graph polynomials are graph parameters invariant under graph isomorphisms which take values in a polynomial ring with a fixed finite number of indeterminates. We study graph polynomials from a model ...theoretic point of view. In this paper we distinguish between the graph theoretic (semantic) and the algebraic (syntactic) meaning of graph polynomials. Graph polynomials appear in the literature either as generating functions, as generalized chromatic polynomials, or as polynomials derived via determinants of adjacency or Laplacian matrices. We show that these forms are mutually incomparable, and propose a unified framework based on definability in Second Order Logic. We show that this comprises virtually all examples of graph polynomials with a fixed finite set of indeterminates. Finally we show that the location of zeros and stability of graph polynomials is not a semantic property. The paper emphasizes a model theoretic view. It gives a unified exposition of classical results in algebraic combinatorics together with new and some of our previously obtained results scattered in the graph theoretic literature.
The mortality pattern of women who began employment as luminizers in the radium dial industry before 1930 was followed through 1990. Hazard models with time-dependent covariates were used on ...mortality data either organized by individual death times or grouped into cross-classified person-year tables. These models were used to quantify trends in mortality associated with either death from or diagnosis of bone sarcoma or head carcinoma. The accumulation of skeletal doses from 226 Ra and 228 Ra was an important predictor of the risk of death from bone sarcoma. Women exposed to 226 Ra at ages associated with active bone growth were at greater risk of bone sarcoma than women receiving even larger exposures at an age when their skeletons would have been fully developed. Exposure to only 226 Ra was found to be an important predictor of risk for carcinoma of the mastoid air cells and paranasal sinuses. For the cranial sites, where adult dimensions are attained early in life, an effect of age at exposure could not be detected.
The reconstruction conjecture has remained open for simple undirected graphs since it was suggested in 1941 by Kelly and Ulam. In an attempt to prove the conjecture, many graph invariants have been ...shown to be reconstructible from the vertex-deleted deck, and in particular, some prominent graph polynomials. Among these are the Tutte polynomial, the chromatic polynomial and the characteristic polynomial. We show that the interlace polynomial, the
U-polynomial, the universal edge elimination polynomial
ξ and the colored versions of the latter two are reconstructible.
We also present a method of reconstructing boolean graph invariants, or in other words, proving recognizability of graph properties (of colored or uncolored graphs), using first order logic.
Graph polynomials are deemed useful if they give rise to algebraic characterizations of various graph properties, and their evaluations encode many other graph invariants. Algebraic: The complete ...graphs Kn and the complete bipartite graphs Kn,n can be characterized as those graphs whose matching polynomials satisfy a certain recurrence relations and are related to the Hermite and Laguerre polynomials. An encoded graph invariant: The absolute value of the chromatic polynomial χ(G,X) of a graph G evaluated at −1 counts the number of acyclic orientations of G.
In this paper we prove a general theorem on graph families which are characterized by families of polynomials satisfying linear recurrence relations. This gives infinitely many instances similar to the characterization of Kn,n. We also show where to use, instead of the Hermite and Laguerre polynomials, linear recurrence relations where the coefficients do not depend on n.
Finally, we discuss the distinctive power of graph polynomials in specific form.
J. Makowsky and B. Zilber (2004) showed that many variations of graph colorings, called CP-colorings in the sequel, give rise to graph polynomials. This is true in particular for harmonious ...colorings, convex colorings, mcct-colorings, and rainbow colorings, and many more. N. Linial (1986) showed that the chromatic polynomial χ(G;X) is #P-hard to evaluate for all but three values X=0,1,2, where evaluation is in P. This dichotomy includes evaluation at real or complex values, and has the further property that the set of points for which evaluation is in P is finite. We investigate how the complexity of evaluating univariate graph polynomials that arise from CP-colorings varies for different evaluation points. We show that for some CP-colorings (harmonious, convex) the complexity of evaluation follows a similar pattern to the chromatic polynomial. However, in other cases (proper edge colorings, mcct-colorings, H-free colorings) we could only obtain a dichotomy for evaluations at non-negative integer points. We also discuss some CP-colorings where we only have very partial results.
A second follow-up of mortality was carried out for workers employed in a thorium-processing plant between 1915 and 1973. The study group comprised 3796 workers (3119 men and 677 women). of the whole ...group, 926 (761 men and 165 women) were deceased and 2620 (2161 men and 459 women) were still alive, while 250 (6.6%) were lost to follow-up.For the male workers, the standardized mortality ratio (SMR) for all causes of death was 1.12 with a 95% confidence interval (95% CI) of 1.05— 1.21. The SMR for the male workers was also significantly increased for all cancers (SMR 1.23, 95% CI 1.04— 1.43) and lung cancer (SMR 1.36, 95% CI 1.02— 1.78).For the female workers, the SMR was 0.74 (95% CI 0.63— 0.86) for all causes and 0.53 (95% CI 0.35— 0.78) for all cancers. The results of a Poisson regression analysis showed that there was no significant effect of the selected factors on lung cancer mortality.
The dichromatic polynomial Z(G;q,v) can be characterized as the most general C-invariant, i.e., a graph polynomial satisfying a linear recurrence with respect to edge deletion and edge contraction. ...Similarly, the universal edge elimination polynomial ξ(G;x,y,z) introduced in Ilya Averbouch, Benny Godlin, and Johann A. Makowsky. An extension of the bivariate chromatic polynomial. Eur. J. Comb, 31(1):1–17, 2010 can be characterized as the most general EE-invariant, i.e., a graph polynomial satisfying a linear recurrence with respect to edge deletion, edge contraction and edge extraction. In this paper we examine substitution instances of ξ(G;x,y,z) and show that among these the dichromatic polynomial Z(G;q,v) plays a distinctive rôle.
The reconstruction conjecture has remained open for simple undirected graphs since it was suggested in 1941 by Kelly and Ulam. In an attempt to prove the conjecture, many graph invariants have been ...shown to be reconstructible from the vertex-deleted deck, and in particular, some prominent graph polynomials. Among these are the Tutte polynomial, the chromatic polynomial and the characteristic polynomial. We show that the interlace polynomial, the U -polynomial, the universal edge elimination polynomial xi and the colored versions of the latter two are reconstructible.
PDF
