Search results for "Conjecture"
showing 10 items of 217 documents
Hartmanis-Stearns Conjecture on Real Time and Transcendence
2012
Hartmanis-Stearns conjecture asserts that any number whose decimal expansion can be computed by a multitape Turing machine is either rational or transcendental. After half a century of active research by computer scientists and mathematicians the problem is still open but much more interesting than in 1965.
On Combinatorial Generation of Prefix Normal Words
2014
A prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. This class of words is important in the context of binary jumbled pattern matching. In this paper we present an efficient algorithm for exhaustively listing the prefix normal words with a fixed length. The algorithm is based on the fact that the language of prefix normal words is a bubble language, a class of binary languages with the property that, for any word w in the language, exchanging the first occurrence of 01 by 10 in w results in another word in the language. We prove that each prefix normal word is produced in O(n) amortized time, and conjecture, based on expe…
Counterexamples to the Kalman Conjectures
2018
In the paper counterexamples to the Kalman conjecture with smooth nonlinearity basing on the Fitts system, that are periodic solution or hidden chaotic attractor are presented. It is shown, that despite the fact that Kalman’s conjecture (as well as Aizerman’s) turned out to be incorrect in the case of n > 3, it had a huge impact on the theory of absolute stability, namely, the selection of the class of nonlinear systems whose stability can be studied with linear methods. peerReviewed
Nonlinear Analysis of Charge-Pump Phase-Locked Loop : The Hold-In and Pull-In Ranges
2021
In this paper a fairly complete mathematical model of CP-PLL, which reliable enough to serve as a tool for credible analysis of dynamical properties of these circuits, is studied. We refine relevant mathematical definitions of the hold-in and pull-in ranges related to the local and global stability. Stability analysis of the steady state for the charge-pump phase locked loop is non-trivial: straight-forward linearization of available CP-PLL models may lead to incorrect conclusions, because the system is not smooth near the steady state and may experience overload. In this work necessary details for local stability analysis are presented and the hold-in range is computed. An upper estimate o…
Fast Matrix Multiplication
2015
Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time O(n2.3755). Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le~Gall has led to an improved algorithm running in time O(n2.3729). These algorithms are obtained by analyzing higher and higher tensor powers of a certain identity of Coppersmith and Winograd. We show that this exact approach cannot result in an algorithm with running time O(n2.3725), and identify a wide class of variants of this approach which cannot result in an algorithm with running time $O(n^{2.3078}); in particular, this approach cannot prove the conjecture that for every e > 0, …
On a class of languages with holonomic generating functions
2017
We define a class of languages (RCM) obtained by considering Regular languages, linear Constraints on the number of occurrences of symbols and Morphisms. The class RCM presents some interesting closure properties, and contains languages with holonomic generating functions. As a matter of fact, RCM is related to one-way 1-reversal bounded k-counter machines and also to Parikh automata on letters. Indeed, RCM is contained in L-NFCM but not in L-DFCM, and strictly includes L-CPA. We conjecture that L-DFCM subset of RCM
On a conjecture about class numbers of totally positive quadratic forms in totally real algebraic number fields
1979
Zusammenfassung Mittels einer fruheren Klassenzahlabschatzung fur quadratische Formen wird als Verallgemeinerung einer Vermutung von Siegel bewiesen, das Geschlechter totalpositiver Formen mit mindestens drei Variablen und vorgegebener Klassenzahl nur in endlich vielen totalreellen algebraischen Zahlkorpern vorkommen. Bei binaren Formen folgt mit einer neuen Klassenzahlformel aus der verallgemeinerten Riemannschen Vermutung dieselbe Aussage. Ohne Annahme einer Hypothese gilt, das die Anzahl der totalreellen Korper eines festen Grades mit totalpositiven binaren Formen vorgegebener Klassenzahl endlich ist.
On deformation of Poisson manifolds of hydrodynamic type
2001
We study a class of deformations of infinite-dimensional Poisson manifolds of hydrodynamic type which are of interest in the theory of Frobenius manifolds. We prove two results. First, we show that the second cohomology group of these manifolds, in the Poisson-Lichnerowicz cohomology, is ``essentially'' trivial. Then, we prove a conjecture of B. Dubrovin about the triviality of homogeneous formal deformations of the above manifolds.
Some contributions to the theory of transformation monoids
2019
The aim of this paper is to present some contributions to the theory of finite transformation monoids. The dominating influence that permutation groups have on transformation monoids is used to describe and characterise transitive transformation monoids and primitive transitive transformation monoids. We develop a theory that not only includes the analogs of several important theorems of the classical theory of permutation groups but also contains substantial information about the algebraic structure of the transformation monoids. Open questions naturally arising from the substantial paper of Steinberg [A theory of transformation monoids: combinatorics and representation theory. Electron. J…
Generalized Braid Groups and Mapping Class Gropus
1997
Given a chord system of D2, we associate a generalized braid group, a surface and a homomorphism from this braid group to the mapping class group of the surface. We disprove a conjecture stated in an article by Perron and Vannier by showing that generally this homomorphism is not injective.