Search results for "Combinatorics"

Structured Frequency Algorithms

2015

B.A. Trakhtenbrot proved that in frequency computability (introduced by G. Rose) it is crucially important whether the frequency exceeds \(\frac{1}{2}\). If it does then only recursive sets are frequency-computable. If the frequency does not exceed \(\frac{1}{2}\) then a continuum of sets is frequency-computable. Similar results for finite automata were proved by E.B. Kinber and H. Austinat et al. We generalize the notion of frequency computability demanding a specific structure for the correct answers. We show that if this structure is described in terms of finite projective planes then even a frequency \(O(\frac{\sqrt{n}}{n})\) ensures recursivity of the computable set. We also show that …

Product Integration for Weakly Singular Integral Equations In ℝm

1985

In this note we discuss the numerical solution of the second kind Fredholm integral equation: $$ y(t) = f(t) + \lambda \int\limits_{\Omega } {{{\psi }_{\alpha }}(|t - s|)g(t,s)y(s)ds,\;t \in \bar{\Omega },} $$ (1) Where \( \lambda \in ;\not{ \subset }\backslash \{ 0\} \) , the functions f,g are given and continuous, |.| denotes the Euclidean norm, and φα, 0 \alpha > 0} \\ {\left\{ {\begin{array}{*{20}{c}} {\ln (r),} & {j = 0} \\ {{{r}^{{ - j}}}} & {j > 0} \\ \end{array} } \right\},\alpha = m} \\ \end{array} ,} \right. $$ with Cj not depending on r. Here Ω _ is the closure of a bounded domain Ω⊂ℝm.

Rigidity transition in two-dimensional random fiber networks

2000

Rigidity percolation is analyzed in two-dimensional random fibrous networks. The model consists of central forces between the adjacent crossing points of the fibers. Two strategies are used to incorporate rigidity: adding extra constraints between second-nearest crossing points with a probability p(sn), and "welding" individual crossing points by adding there four additional constraints with a probability p(weld), and thus fixing the angles between the fibers. These additional constraints will make the model rigid at a critical probability p(sn)=p(sn)(c) and p(weld)=p(weld)(c), respectively. Accurate estimates are given for the transition thresholds and for some of the associated critical e…

Rigidity of random networks of stiff fibers in the low-density limit.

2001

Rigidity percolation is analyzed in two-dimensional random networks of stiff fibers. As fibers are randomly added to the system there exists a density threshold ${q=q}_{\mathrm{min}}$ above which a rigid stress-bearing percolation cluster appears. This threshold is found to be above the connectivity percolation threshold ${q=q}_{c}$ such that ${q}_{\mathrm{min}}=(1.1698\ifmmode\pm\else\textpm\fi{}{0.0004)q}_{c}.$ The transition is found to be continuous, and in the universality class of the two-dimensional central-force rigidity percolation on lattices. At percolation threshold the rigid backbone of the percolating cluster was found to break into rigid clusters, whose number diverges in the…

K-theory of function rings

1990

AbstractThe ring R of continuous functions on a compact topological space Xwith values in R or C is considered. It is shown that the algebraic K-theory of such rings with coefficients in ZkZ, k any positive integer, agrees with the topological K-theory of the underlying space X with the same coefficient rings. The proof is based on the result that the map from Rδ (R with discrete topology) to R (R with compact-open topology) induces a natural isomorphism between the homologies with coefficients in ZkZ of the classifying spaces of the respective infinite general linear groups. Some remarks on the situation with X not compact are added.

Equidistribution and Counting of Rational Points in Completed Function Fields

2019

Let K be a (global) function field over Fq of genus g, let v be a (normalised discrete) valuation of K, let Kv be the associated completion of K, and let Rv be the affine function ring associated with v.

An algorithm for the Rural Postman problem on a directed graph

1986

The Directed Rural Postman Problem (DRPP) is a general case of the Chinese Postman Problem where a subset of the set of arcs of a given directed graph is ‘required’ to be traversed at minimum cost. If this subset does not form a weakly connected graph but forms a number of disconnected components the problem is NP-Complete, and is also a generalization of the asymmetric Travelling Salesman Problem. In this paper we present a branch and bound algorithm for the exact solution of the DRPP based on bounds computed from Lagrangean Relaxation (with shortest spanning arborescence sub-problems) and on the fathoming of some of the tree nodes by the solution of minimum cost flow problems. Computation…

Stationary Point Processes

2008

A generalization of Sardinas and Patterson's algorithm to z-codes

1993

Abstract This paper concerns the framework of z-codes theory. The main contribution consists in an extension of the algorithm of Sardinas and Patterson for deciding whether a finite set of words X is a z-code. To improve the efficiency of this test we have found a tight upper bound on the length of the shortest words that might have a double z-factorization over X. Some remarks on the complexity of the algorithm are also given. Moreover, a slight modification of this algorithm allows us to compute the z-deciphering delay of X.

Spectral density of the correlation matrix of factor models: a random matrix theory approach.

2005

We studied the eigenvalue spectral density of the correlation matrix of factor models of multivariate time series. By making use of the random matrix theory, we analytically quantified the effect of statistical uncertainty on the spectral density due to the finiteness of the sample. We considered a broad range of models, ranging from one-factor models to hierarchical multifactor models.