On the cardinality and complexity of the set of codings for self-similar sets with positive Lebesgue measure

Let λ1,…,λn be real numbers in (0,1) and p1,…,pn be points in Rd. Consider the collection of maps fj:Rd→Rd given by fj(x)=λjx+(1−λj)pj. It is a well known result that there exists a unique nonempty compact set Λ⊂Rd satisfying Λ=∪nj=1fj(Λ). Each x∈Λ has at least one coding, that is a sequence (ϵi)∞i=1 ∈{1,…,n}N that satisfies limN→∞fϵ1…fϵN(0)=x. We study the size and complexity of the set of codings of a generic x∈Λ when Λ has positive Lebesgue measure. In particular, we show that under certain natural conditions almost every x∈Λ has a continuum of codings. We also show that almost every x∈Λ has a universal coding. Our work makes no assumptions on the existence of holes in Λ and improves upon existing results when it is assumed Λ contains no holes.

A group topology on the free abelian group of cardinality c that makes its square countably compact

Under p = c, we prove that it is possible to endow the free abelian group of cardinality c with a group topology that makes its square countably compact. This answers a question posed by Madariaga-Garcia and Tomita and by Tkachenko. We also prove that there exists a Wallace semigroup (i.e., a countably compact both-sided cancellative topological semigroup which is not a topological group) whose square is countably compact. This answers a question posed by Grant.

Computable Diagonalizations and Turing’s Cardinality Paradox

A. N. Turing’s 1936 concept of computability, computing machines, and computable binary digital sequences, is subject to Turing’s Cardinality Paradox. The paradox conjoins two opposed but comparably powerful lines of argument, supporting the propositions that the cardinality of dedicated Turing machines outputting all and only the computable binary digital sequences can only be denumerable, and yet must also be nondenumerable. Turing’s objections to a similar kind of diagonalization are answered, and the implications of the paradox for the concept of a Turing machine, computability, computable sequences, and Turing’s effort to prove the unsolvability of the Entscheidungsproblem, are explained in light of the paradox. A solution to Turing’s Cardinality Paradox is proposed, positing a higher geometrical dimensionality of machine symbol-editing information processing and storage media than is available to canonical Turing machine tapes. The suggestion is to add volume to Turing’s discrete two-dimensional machine tape squares, considering them instead as similarly ideally connected massive three-dimensional machine information cells. Three-dimensional computing machine symbol-editing information processing cells, as opposed to Turing’s two-dimensional machine tape squares, can take advantage of a denumerably infinite potential for parallel digital sequence computing, by which to accommodate denumerably infinitely many computable diagonalizations. A three-dimensional model of machine information storage and processing cells is recommended on independent grounds as better representing the biological realities of digital information processing isomorphisms in the three-dimensional neural networks of living computers.

On the Set of Locally Convex Topologies Compatible with a Given Topology on a Vector Space: Cardinality Aspects

For a topological vector space (X, τ ), we consider the family LCT (X, τ ) of all locally convex topologies defined on X, which give rise to the same continuous linear functionals as the original topology τ . We prove that for an infinite-dimensional reflexive Banach space (X, τ ), the cardinality of LCT (X, τ ) is at least c.

Extremal problems on sum-free sets and coverings in tridimensional spaces

Given a prime power q, define c (q) as the minimum cardinality of a subset H of F 3 q which satisfies the following property: every vector in this space di ff ers in at most 1 coordinate from a multiple of a vector in H. In this work, we introduce two extremal problems in combinatorial number theory aiming to discuss a known connection between the corresponding coverings and sum-free sets. Also, we provide several bounds on these maps which yield new classes of coverings, improving the previous upper bound on c (q)

Flat tori, lattices and bounds for commutative group codes

We show that commutative group spherical codes in R(n), as introduced by D. Slepian, are directly related to flat tori and quotients of lattices. As consequence of this view, we derive new results on the geometry of these codes and an upper bound for their cardinality in terms of minimum distance and the maximum center density of lattices and general spherical packings in the half dimension of the code. This bound is tight in the sense it can be arbitrarily approached in any dimension. Examples of this approach and a comparison of this bound with Union and Rankin bounds for general spherical codes is also presented.

Should optional properties be used in conceptual modelling? A theory and three empirical tests

An important feature of some conceptual modelling grammars is the features they provide to allow database designers to show real-world things may or may not possess a particular attribute or relationship. In the entity-relationship model, for example, the fact that a thing may not possess an attribute can be represented by using a special symbol to indicate that the attribute is optional. Similarly, the fact that a thing may or may not be involved in a relationship can be represented by showing the minimum cardinality of the relationship as zero. Whether these practices should be followed, however, is a contentious issue. An alternative approach is to eliminate optional attributes and relationships from conceptual schema diagrams by using subtypes that have only mandatory attributes and relationships. In this paper, we first present a theory that led us to predict that optional attributes and relationships should be used in conceptual schema diagrams only when users of the diagrams require a surface-level understanding of the domain being represented by the diagrams. When users require a deep-level understanding, however, optional attributes and relationships should not be used because they undermine users' abilities to grasp important domain semantics. We describe three experiments which we then undertook to test our predictions. The results of the experiments support our predictions.

Branching processes and computational collapse of discretized unimodal mappings

In computer simulations of smooth dynamical systems, the original phase space is replaced by machine arithmetic, which is a finite set. The resulting spatially discretized dynamical systems do not inherit all functional properties of the original systems, such as surjectivity and existence of absolutely continuous invariant measures. This can lead to computational collapse to fixed points or short cycles. The paper studies loss of such properties in spatial discretizations of dynamical systems induced by unimodal mappings of the unit interval. The problem reduces to studying set-valued negative semitrajectories of the discretized system. As the grid is refined, the asymptotic behavior of the cardinality structure of the semitrajectories follows probabilistic laws corresponding to a branching process. The transition probabilities of this process are explicitly calculated. These results are illustrated by the example of the discretized logistic mapping.

A cognitive complexity metric applied to cognitive development

Two experiments tested predictions from a theory in which processing load depends on relational complexity (RC), the number of variables related in a single decision. Tasks from six domains (transitivity, hierarchical classification, class inclusion, cardinality, relative-clause sentence comprehension, and hypothesis testing) were administered to children aged 3-8 years. Complexity analyses indicated that the domains entailed ternary relations (three variables). Simpler binary-relation (two variables) items were included for each domain. Thus RC was manipulated with other factors tightly controlled. Results indicated that (i) ternary-relation items were more difficult than comparable binary-relation items, (ii) the RC manipulation was sensitive to age-related changes, (iii) ternary relations were processed at a median age of 5 years, (iv) cross-task correlations were positive, with all tasks loading on a single factor (RC), (v) RC factor scores accounted for 80% (88%) of age-related variance in fluid intelligence (compositionality of sets), (vi) binary- and ternary-relation items formed separate complexity classes, and (vii) the RC approach to defining cognitive complexity is applicable to different content domains. (C) 2002 Elsevier Science (USA). All rights reserved.

More on exact bicoverings of 12 points

The minimum number of incomplete blocks required to cover, exactly lambda times, all t-element subsets from a set V of cardinality v (v > t) is denoted by y(lambda, t; v). The value of g(2, 2; v) is known for v = 3, 4,..., 11. It was previously known that 14 less than or equal to g(2, 2; 12) less than or equal to 16. We prove that g(2, 2; 12) greater than or equal to 15.

Constraint solving over multi-valued logics - application to digital circuits

Due to usage conditions, hazardous environments or intentional causes, physical and virtual systems are subject to faults in their components, which may affect their overall behaviour. In a ‘black-box’ agent modelled by a set of propositional logic rules, in which just a subset of components is externally visible, such faults may only be recognised by examining some output function of the agent. A (fault-free) model of the agent’s system provides the expected output given some input. If the real output differs from that predicted output, then the system is faulty. However, some faults may only become apparent in the system output when appropriate inputs are given. A number of problems regarding both testing and diagnosis thus arise, such as testing a fault, testing the whole system, finding possible faults and differentiating them to locate the correct one. The corresponding optimisation problems of finding solutions that require minimum resources are also very relevant in industry, as is minimal diagnosis. In this dissertation we use a well established set of benchmark circuits to address such diagnostic related problems and propose and develop models with different logics that we formalise and generalise as much as possible. We also prove that all techniques generalise to agents and to multiple faults. The developed multi-valued logics extend the usual Boolean logic (suitable for faultfree models) by encoding values with some dependency (usually on faults). Such logics thus allow modelling an arbitrary number of diagnostic theories. Each problem is subsequently solved with CLP solvers that we implement and discuss, together with a new efficient search technique that we present. We compare our results with other approaches such as SAT (that require substantial duplication of circuits), showing the effectiveness of constraints over multi-valued logics, and also the adequacy of a general set constraint solver (with special inferences over set functions such as cardinality) on other problems. In addition, for an optimisation problem, we integrate local search with a constructive approach (branch-and-bound) using a variety of logics to improve an existing efficient tool based on SAT and ILP.

On the ranks of certain monoids of transformations that preserve a uniform partition

The rank of a semigroup, an important and relevant concept in Semigroup Theory, is the cardinality of a least-size generating set. Semigroups of transformations that preserve or reverse the order or the orientation as well as semigroups of transformations preserving an equivalence relation have been widely studied over the past decades by many authors. The purpose of this article is to compute the ranks of the monoid

Database repairs with answer set programming

Dissertação para obtenção do Grau de Mestre em Engenharia Informática