Investigation of binary spectra by explicit polynomial transformations of graphs
type: Item
instance of: scholarly article
title: Investigation of binary spectra by explicit polynomial transformations of graphs
zbMATH Open document ID: 0797.03030
DOI: 10.1016/0304-3975(92)00018-M
author: Malika More
published in: Theoretical Computer Science
publication date: 1994-04-05T00:00:00Z
review text: Let \(L\) be a first-order language with identity whose specific symbols are only binary predicate symbols \(P_ 1,\dots,P_ n\) \((n\in N)\). For any \(L\)-sentence \(\alpha\), \(S(\alpha)\) denotes the set of cardinalities of finite models of \(\alpha\). It is proved that for any \(L\)-sentence \(\alpha\) and any polynomial \(f\) of \(Z[x]\) asymptotically greater than or equal to the identity function on \(N\), there exists an \(L\)-sentence \(\beta\) such that \(S(\beta)= f(S(\alpha))\), and that if \(f\) is of degree \(k\) and \(P_ n\) not contained in \(\alpha\) for \(n\geq q+1\), then \(P_ n\) is not contained in \(\beta\) for \(n\geq 2q+ k\) if \(k<3\) and for \(n\geq q+ k+1\) if \(k\geq 3\).
Mathematics Subject Classification ID: 03C13
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 03D55
zbMATH DE Number: 540857
zbMATH Keywords: spectrum of first-order sentence
zbMATH Keywords: polynomial transformations
MaRDI profile type: Publication
cites work: Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität
cites work: Q5830955
cites work: A spectrum hierarchy
cites work: Universal quantifiers and time complexity of random access machines
cites work: First-order spectra with one variable
cites work: Q4159038
cites work: Complexity classes and theories of finite models
cites work: Q3218118
Recommended article: Q4340262
Recommended article: Spectra of digraph transformations
Recommended article: Characteristic polynomials and spectra of Boolean graphs
Recommended article: Lexicographic polynomials of graphs and their spectra
Recommended article: On spectra of expansion graphs and matrix polynomials
Recommended article: Spectra of Boolean graphs and certain matrices of binomial coefficients
Recommended article: Q4014856
Recommended article: Adjacency polynomials of digraph transformations
Recommended article: Spectra of regular graphs and hypergraphs and orthogonal polynomials
Recommended article: Laplacian spectra of digraph transformations
description: scientific article; zbMATH DE number 540857