Response curves of deterministic and probabilistic cellular automata in one and two dimensions

One of the most important problems in the theory of cellular automata (CA) is determining the proportion of cells in a specific state after a given number of time iterations. We approach this problem using patterns in preimage sets - that is, the set of blocks which iterate to the desired output. This allows us to construct a response curve - a relationship between the proportion of cells in state 1 after niterations as a function of the initial proportion. We derive response curve formulae for many two-dimensional deterministic CA rules with L-neighbourhood. For all remaining rules, we find experimental response curves. We also use preimage sets to classify surjective rules. In the last part of the thesis, we consider a special class of one-dimensional probabilistic CA rules. We find response surface formula for these rules and experimental response surfaces for all remaining rules.

Generating Relation Algebras for Qualitative Spatial Reasoning

Basic relationships between certain regions of space are formulated in natural language in everyday situations. For example, a customer specifies the outline of his future home to the architect by indicating which rooms should be close to each other. Qualitative spatial reasoning as an area of artificial intelligence tries to develop a theory of space based on similar notions. In formal ontology and in ontological computer science, mereotopology is a first-order theory, embodying mereological and topological concepts, of the relations among wholes, parts, parts of parts, and the boundaries between parts. We shall introduce abstract relation algebras and present their structural properties as well as their connection to algebras of binary relations. This will be followed by details of the expressiveness of algebras of relations for region based models. Mereotopology has been the main basis for most region based theories of space. Since its earliest inception many theories have been proposed for mereotopology in artificial intelligence among which Region Connection Calculus is most prominent. The expressiveness of the region connection calculus in relational logic is far greater than its original eight base relations might suggest. In the thesis we formulate ways to automatically generate representable relation algebras using spatial data based on region connection calculus. The generation of new algebras is a two pronged approach involving splitting of existing relations to form new algebras and refinement of such newly generated algebras. We present an implementation of a system for automating aforementioned steps and provide an effective and convenient interface to define new spatial relations and generate representable relational algebras.

Region Connection Calculus: Composition Tables and Constraint Satisfaction Problems

Qualitative spatial reasoning (QSR) is an important field of AI that deals with qualitative aspects of spatial entities. Regions and their relationships are described in qualitative terms instead of numerical values. This approach models human based reasoning about such entities closer than other approaches. Any relationships between regions that we encounter in our daily life situations are normally formulated in natural language. For example, one can outline one's room plan to an expert by indicating which rooms should be connected to each other. Mereotopology as an area of QSR combines mereology, topology and algebraic methods. As mereotopology plays an important role in region based theories of space, our focus is on one of the most widely referenced formalisms for QSR, the region connection calculus (RCC). RCC is a first order theory based on a primitive connectedness relation, which is a binary symmetric relation satisfying some additional properties. By using this relation we can define a set of basic binary relations which have the property of being jointly exhaustive and pairwise disjoint (JEPD), which means that between any two spatial entities exactly one of the basic relations hold. Basic reasoning can now be done by using the composition operation on relations whose results are stored in a composition table. Relation algebras (RAs) have become a main entity for spatial reasoning in the area of QSR. These algebras are based on equational reasoning which can be used to derive further relations between regions in a certain situation. Any of those algebras describe the relation between regions up to a certain degree of detail. In this thesis we will use the method of splitting atoms in a RA in order to reproduce known algebras such as RCC15 and RCC25 systematically and to generate new algebras, and hence a more detailed description of regions, beyond RCC25.

The Role of Experience in the Organization and Refinement of Face Space

Adults code faces in reference to category-specific norms that represent the different face categories encountered in the environment (e.g., race, age). Reliance on such norm-based coding appears to aid recognition, but few studies have examined the development of separable prototypes and the way in which experience influences the refinement of the coding dimensions associated with different face categories. The present dissertation was thus designed to investigate the organization and refinement of face space and the role of experience in shaping sensitivity to its underlying dimensions. In Study 1, I demonstrated that face space is organized with regard to norms that reflect face categories that are both visually and socially distinct. These results provide an indication of the types of category-specific prototypes that can conceivably exist in face space. Study 2 was designed to investigate whether children rely on category-specific prototypes and the extent to which experience facilitates the development of separable norms. I demonstrated that unlike adults and older children, 5-year-olds rely on a relatively undifferentiated face space, even for categories with which they receive ample experience. These results suggest that the dimensions of face space undergo significant refinement throughout childhood; 5 years of experience with a face category is not sufficient to facilitate the development of separable norms. In Studies 3 through 5, I examined how early and continuous exposure to young adult faces may optimize the face processing system for the dimensions of young relative to older adult faces. In Study 3, I found evidence for a young adult bias in attentional allocation among young and older adults. However, whereas young adults showed an own-age recognition advantage, older adults exhibited comparable recognition for young and older faces. These results suggest that despite the significant experience that older adults have with older faces, the early and continuous exposure they received with young faces continues to influence their recognition, perhaps because face space is optimized for young faces. In Studies 4 and 5, I examined whether sensitivity to deviations from the norm is superior for young relative to older adult faces. I used normality/attractiveness judgments as a measure of this sensitivity; to examine whether biases were specific to norm-based coding, I asked participants to discriminate between the same faces. Both young and older adults were more accurate when tested with young relative to older faces—but only when judging normality. Like adults, 3- and 7-year-olds were more accurate in judging the attractiveness of young faces; however, unlike adults, this bias extended to the discrimination task. Thus by 3 years of age children are more sensitive to differences among young relative to older faces, suggesting that young children's perceptual system is more finely tuned for young than older adult faces. Collectively, the results of this dissertation help elucidate the development of category-specific norms and clarify the role of experience in shaping sensitivity to the dimensions of face space.