A caracterização estática dos sistemas caóticos clássicos dissipativos tem sido realizada através do cálculo das dimensões generalizadas \'D IND. q\' e do espectro de singularidades f(alfa). Os métodos mais comuns de cálculo numérico dessas funções utilizam algoritmos de contagem de caixa. Porém, esses algoritmos produzem um erro sistemático através de \'caixas espúrias\', levando a resultados distorcidos. Por essa razão, estudamos métodos numéricos que não utilizam o algoritmo de contagem de caixa, verificando em que casos eles podem ser aplicados eficazmente e propusemos um novo algoritmo de contagem de caixa que reduz o número de \'caixas espúrias\', obtendo melhores resultados. / The static caracterization of classical dissipative chaotical systems has been achieved by the calculation of the generalized dimensions \'D IND. q\' and the spectrum of singularities f(alfa). The most used numerical methods of evaluating these functions are based on box counting algorithms. The results obtained by those methods are distorced by the presence of \'spurious boxes\' generated intrinsecally by these algorithms. For this reason, we have studied numerical methods that don\'t use box counting algorithms, and we have tried to verify in which kind of sets they give best results. We also have proposed a new box counting algorithm that reduces the number of \'spurious boxes\', and led to better results.

Szemerédi's Regularity Lemma is powerful tool in Graph Theory, yielding many applications in areas such as Extremal Graph Theory, Combinatorial Number Theory and Theoretical Computer Science. Strong hypergraph extensions of graph regularity techniques were recently given by Nagle, Rödl, Schacht and Skokan, by W.T. Gowers, and subsequently, by T. Tao. These extensions have yielded quite a few non-trivial applications to Extremal Hypergraph Theory, Combinatorial Number Theory and Theoretical Computer Science. A main drawback to the hypergraph regularity techniques above is that they are highly technical. In this thesis, we consider a less technical version of hypergraph regularity which more directly generalizes Szemeredi's regularity lemma for graphs. The tools we discuss won't yield all applications of their stronger relatives, but yield still several applications in extremal hypergraph theory (for so-called linear or simple hypergraphs), including algorithmic ones. This thesis surveys these lighter regularity techiques, and develops three applications of them.

No description available.

Call number: LD2668 .T4 1985 L43 / Master of Science

Call number: LD2668 .T4 1985 W36 / Master of Science

In this thesis we investigate practical aspects related to point counting problems on algebraic varieties over finite fields. In particular, we present significant improvements to Lauder’s deformation method for smooth projective hypersurfaces, which allow this method to be successfully applied to previously intractable instances. Part I is dedicated to the deformation method, including a complete description of the algorithm but focussing on aspects for which we contribute original improvements. In Chapter 3 we describe the computation of the action of Frobenius on the rigid cohomology space associated to a diagonal hypersurface; in Chapter 4 we develop a method for fast computations in the de Rham cohomology spaces associated to the family, which allows us to compute the Gauss–Manin connection matrix. We conclude this part with a small selection of examples in Chapter 6. In Part II we present an improvement to Lauder’s fibration method. We manage to resolve the bottleneck in previous computation, which is formed by so-called polynomial radix conversions, employing power series inverses and a more efficient implementation. Finally, Part III is dedicated to a comprehensive treatment of the arithmetic in unramified extensions of Qp , which is connected to the previous parts where our computations rely on efficient implementations of p-adic arithmetic. We have made these routines available for others in FLINT as individual modules for p-adic arithmetic.

This thesis concerns the formulation of novel developmental robotics models of embodied phenomena in number learning. Learning to count is believed to be of paramount importance for the acquisition of the remarkable fluency with which humans are able to manipulate numbers and other abstract concepts derived from them later in life. The ever-increasing amount of evidence for the embodied nature of human mathematical thinking suggests that the investigation of numerical cognition with the use of robotic cognitive models has a high potential of contributing toward the better understanding of the involved mechanisms. This thesis focuses on two particular groups of embodied effects tightly linked with learning to count. The first considered phenomenon is the contribution of the counting gestures to the counting accuracy of young children during the period of their acquisition of the skill. The second phenomenon, which arises over a longer time scale, is the human tendency to internally associate numbers with space that results, among others, in the widely-studied SNARC effect. The PhD research contributes to the knowledge in the subject by formulating novel neuro-robotic cognitive models of these phenomena, and by employing these in two series of simulation experiments. In the context of the counting gestures the simulations provide evidence for the importance of learning the number words prior to learning to count, for the usefulness of the proprioceptive information connected with gestures to improving counting accuracy, and for the significance of the spatial correspondence between the indicative acts and the objects being enumerated. In the context of the model of spatial-numerical associations the simulations demonstrate for the first time that these may arise as a consequence of the consistent spatial biases present when children are learning to count. Finally, based on the experience gathered throughout both modelling experiments, specific guidelines concerning future efforts in the application of robotic modelling in mathematical cognition are formulated.

In this dissertation we study the Laplace operator acting on functions on a smooth, compact Riemannian manifold. Our approach is based on the study of the spectrum of the aforementioned operator. The main objects of our interest are the counting function of the Laplacian and its Riesz means. We discuss the asymptotics of aforementioned functions when the argument approaches infinity.

We define instance compressibility ([13, 17]) for parametric problems in the classes PH and PSPACE.We observe that the problem ƩiCIRCUITSAT of deciding satisfiability of a quantified Boolean circuit with i-1 alternations of quantifiers starting with an existential quantifier is complete for parametric problems in the class Ʃp/i with respect to w-reductions, and that analogously the problem QBCSAT (Quantified Boolean Circuit Satisfiability) is complete for parametric problems in PSPACE with respect to w-reductions. We show the following results about these problems: 1. If CIRCUITSAT is non-uniformly compressible within NP, then ƩiCIRCUITSAT is non-uniformly compressible within NP, for any i≥1. 2. If QBCSAT is non-uniformly compressible (or even if satisfiability of quantified Boolean CNF formulae is non-uniformly compressible), then PSPACE ⊆ NP/poly and PH collapses to the third level. Next, we define Succinct Interactive Proof (Succinct IP) and by adapting the proof of IP = PSPACE ([11, 6]) , we show that QBCNFSAT (Quantified Boolean Formula (in CNF) Satisfiability) is in Succinct IP. On the contrary if QBCNFSAT has Succinct PCPs ([32]) , Polynomial Hierarchy (PH) collapses. After extending the notion of instance compression to higher classes, we study the hierarchical structure of the parametric problems with respect to compressibility. For that purpose, we extend the existing definition of VC-hierarchy ([13]) to parametric problems. After that, we have considered a long list of natural NP problems and tried to classify them into some level of VC-hierarchy. We have shown some of the new w-reductions in this context and pointed out a few interesting results including the ones as follows. 1. CLIQUE is VC1-complete (using the results in [14]). 2. SET SPLITTING and NAE-SAT are VC2-complete. We have also introduced a new complexity class VCE in this context and showed some hardness and completeness results for this class. We have done a comparison of VC-hierarchy with other related hierarchies in parameterized complexity domain as well. Next, we define the compression of counting problems and the analogous classification of them with respect to the notion of instance compression. We define #VC-hierarchy for this purpose and similarly classify a large number of natural counting problems with respect to this hierarchy, by showing some interesting hardness and completeness results. We have considered some of the interesting practical problems as well other than popular NP problems (e.g., #MULTICOLOURED CLIQUE, #SELECTED DOMINATING SET etc.) and studied their complexity for both decision and counting version. We have also considered a large variety of circuit satisfiability problems (e.g., #MONOTONE WEIGHTED-CNFSAT, #EXACT DNF-SAT etc.) and proved some interesting results about them with respect to the theory of instance compressibility.

This paper gives a brief introduction into the fundaments of knot theory: introducing knot diagrams, knot invariants, and two techniques to determine whether or not two knots are ambient isotopic. After discussing the basics of knot theory an algebraic coloring of knots knows as a bikei is introduced. The algebraic structure as well as the various axioms that define a bikei are defined. Furthermore, an extension between the Alexander polynomial of a knot and the Alexander Bikei is made. The remainder of the paper is devoted to reintroducing a modified homology and cohomology theory for involutory biquandles known as bikei, first introduced in [18]. The bikei 2-cocycles can be utilized to enhance the counting invariant for unoriented knots and links as well as unoriented and non-orienteable knotted surfaces in R4.