Search results for "Theoretical Computer Science"

A grid ant colony algorithm for the orienteering problem

2005

In this paper we propose a distributed ant colony algorithm to solve large scale orienteering problem instances. Our approach is based on a multi-colony strategy where each colony works in an independent portion (cluster) in the original graph. This results in no need for communicating pheromones information among colonies and in increasing speedup. We have implemented our algorithm as a .NET Web services infrastructure following a grid computing philosophy and we provide some promising experimental results to show the feasibility and effectiveness of our approach

A simple windows program for coding fast-changing events in observational situations divided into variable intervals

1996

A Language Shift Simulation Based on Cellular Automata

2011

Language extinction is a widespread social phenomenon affecting several million people throughout the world today. By the end of this century, more than 5100 of the approximately 6000 languages currently spoken around the world will have disappeared. This is mainly because of language shifts, i.e., because a community of speakers stops using their traditional language and speaks a new one in all communication settings. In this study, the authors present the properties of a cellular automaton that incorporates some assumptions from the Gaelic-Arvanitika model of language shifts and the findings on the dynamics of social impacts in the field of social psychology. To assess the cellular automa…

Diagrammatic approach to cellular automata and the emergence of form with inner structure

2018

We present a diagrammatic method to build up sophisticated cellular automata (CAs) as models of complex physical systems. The diagrams complement the mathematical approach to CA modeling, whose details are also presented here, and allow CAs in rule space to be classified according to their hierarchy of layers. Since the method is valid for any discrete operator and only depends on the alphabet size, the resulting conclusions, of general validity, apply to CAs in any dimension or order in time, arbitrary neighborhood ranges and topology. We provide several examples of the method, illustrating how it can be applied to the mathematical modeling of the emergence of order out of disorder. Specif…

Researching Conditional Probability Problem Solving

2014

The chapter is organized into two parts. In the first one, the main protagonist is the conditional probability problem. We show a theoretical study about conditional probability problems, identifying a particular family of problems we call ternary problems of conditional probability. We define the notions of Level, Category and Type of a problem in order to classify them into sub-families and in order to study them better. We also offer a tool we call trinomial graph that functions as a generative model for this family of problems. We show the syntax of the model that allows researchers and teachers to translate a problem in terms of the trinomial graphs language, and the consequences of th…

Mesh connectivity compression using convection reconstruction

2007

International audience; During a highly productive period running from 1995 to about 2002, the research in lossless compression of 3D meshes mainly consisted in a hard battle for the best bitrates. But for a few years, compression rates seem stabilized around 1.5 bit per vertex for the connectivity coding of usual meshes, and more and more work is dedicated to remeshing, lossy compression, or gigantic mesh compression, where memory and CPU optimizations are the new priority. However, the size of 3D models keeps growing, and many application fields keep requiring lossless compression. In this paper, we present a new contribution for single-rate lossless connectivity compression, which first …

Multi-Dimensional motivic pattern extraction founded on adaptive redundancy filtering

2005

Abstract We present a computational model for discovering repeated patterns in symbolic representations of monodic music. Patterns are discovered through an incremental adaptive identification along a multi-dimensional parametric space. The difficulties of pattern discovery mainly come from combinatorial redundancies, that our model is able to control efficiently. A specificity relation is defined between pattern descriptions, unifying suffix and inclusion relations and enabling a filtering of redundant descriptions. Combinatorial proliferation caused by successive repetitions of patterns is managed using cyclic patterns. The modelling of these redundancy control mechanisms enables an autom…

New Representations for Multidimensional Functions Based on Kolmogorov Superposition Theorem. Applications on Image Processing

2012

Mastering the sorting of the data in signal (nD) can lead to multiple applications like new compression, transmission, watermarking, encryption methods and even new processing methods for image. Some authors in the past decades have proposed to use these approaches for image compression, indexing, median filtering, mathematical morphology, encryption. A mathematical rigorous way for doing such a study has been introduced by Andrei Nikolaievitch Kolmogorov (1903-1987) in 1957 and recent results have provided constructive ways and practical algorithms for implementing the Kolmogorov theorem. We propose in this paper to present those algorithms and some preliminary results obtained by our team…

Robustness and Randomness

2008

The study of robustness problems for computational geometry algorithms is a topic that has been subject to intensive research efforts from both computer science and mathematics communities. Robustness problems are caused by the lack of precision in computations involving floating-point instead of real numbers. This paper reviews methods dealing with robustness and inaccuracy problems. It discusses approaches based on exact arithmetic, interval arithmetic and probabilistic methods. The paper investigates the possibility to use randomness at certain levels of reasoning to make geometric constructions more robust.

More Power through Symbolic Computation: Extending Stata by using the Maxima Computer algebra system

2015

Maxima is a free and open-source computer algebra system that can perform symbolic computations such as solving equations, determining derivatives of functions, obtaining Taylor series, and manipulating algebraic expressions. In this article, I present the Maxima Bridge System, which is a collection of software programs that allows Stata to interface with Maxima so that Maxima can be used for symbolic computation to transfer data from Stata to Maxima and to retrieve results from Maxima. The cooperation between Stata and Maxima provides an environment for statistical analysis in which symbolic computation can be easily used together with all the facilities supplied by Stata. In this environ…