Search results for "Theoretical Computer Science"

On the lattice of prefix codes

2002

AbstractThe natural correspondence between prefix codes and trees is explored, generalizing the results obtained in Giammarresi et al. (Theoret. Comput. Sci. 205 (1998) 1459) for the lattice of finite trees under division and the lattice of finite maximal prefix codes. Joins and meets of prefix codes are studied in this light in connection with such concepts as finiteness, maximality and varieties of rational languages. Decidability results are obtained for several problems involving rational prefix codes, including the solution to the primeness problem.

On the decomposition of prefix codes

2017

Abstract In this paper we focus on the decomposition of rational and maximal prefix codes. We present an effective procedure that allows us to decide whether such a code is decomposable. In this case, the procedure also produces the factors of some of its decompositions. We also give partial results on the problem of deciding whether a rational maximal prefix code decomposes over a finite prefix code.

Design of efficient codes for the AWGN channel based on decomposable binary lattices

1998

This work is concerned with the use of binary decomposable lattice codes over the QAM Gaussian channel. First, we investigate the structure of such class of lattices: we derive consistency conditions for the binary codes appearing in their decomposition and express their nominal coding gain and some bounds for their error coefficient in terms of the parameters of the component codes. Then we describe a general multistage bounded‐distance decoding algorithm with low complexity and we evaluate its performance. Finally, we develop a design example and report the corresponding simulation results; as a reference some comparisons with standard TCM codes are also presented.

Exacus: Efficient and Exact Algorithms for Curves and Surfaces

2005

We present the first release of the Exacus C++ libraries. We aim for systematic support of non-linear geometry in software libraries. Our goals are efficiency, correctness, completeness, clarity of the design, modularity, flexibility, and ease of use. We present the generic design and structure of the libraries, which currently compute arrangements of curves and curve segments of low algebraic degree, and boolean operations on polygons bounded by such segments.

Burrows–Wheeler transform and Sturmian words

2003

Surface Reconstruction Based on a Descriptive Approach

2000

The design of complex surfaces is generally hard to achieve. A natural method consists in the subdivision of the global surface into basic surface elements. The different elements are independently designed and then assembled together to represent the final surface. This method requires a classification and a formal description of the basic elements. This chapter presents a general framework for surface description, based on a constructive tree approach. In this tree the leaves are surface primitives and the nodes are constructive operators.

Construction of pseudo-random sequences from chaos

2002

Exponential instability in the fractional Calder\'on problem

2017

In this note we prove the exponential instability of the fractional Calder\'on problem and thus prove the optimality of the logarithmic stability estimate from \cite{RS17}. In order to infer this result, we follow the strategy introduced by Mandache in \cite{M01} for the standard Calder\'on problem. Here we exploit a close relation between the fractional Calder\'on problem and the classical Poisson operator. Moreover, using the construction of a suitable orthonormal basis, we also prove (almost) optimality of the Runge approximation result for the fractional Laplacian, which was derived in \cite{RS17}. Finally, in one dimension, we show a close relation between the fractional Calder\'on pro…

Modeling Local Social Migrations: A Cellular Automata Approach

2015

In local social migrations, agents move from their initial location looking for a better local social environment. Social migrations processes do not change the number of social agents of a given type (i.e., the empirical distribution of the population) but their spatial location. Although cellular automata seems to appear as a natural approach to model of social migrations, the evolution of the configuration through a cellular automata might induce a new configuration wherein the number of agents of each type might be actually modified. This article provides a characterization of these cellular automata rules such that for any initial empirical distribution, the evolution of the configurat…

Social Simulation Based on Cellular Automata: Modeling Language Shifts

2011

Nowadays, language shifts (i.e., a community of speakers stops using their traditional language and speaks a new one in all communication settings) may produce a massive extinction of languages throughout the world. In this context, an important task for social sciences research should therefore be to achieve a deep comprehension of language shifts. However, modeling the social and behavioral variables that guide the social behavior of individuals and groups has traditionally been tricky in all the social sciences. In this situation, social simulation provides a tool for testing hypotheses and building models of social phenomena (see, for example, Gilbert, 1996; Gilbert & Toitzsch, 2005; an…