Planar Polyline Drawings via Graph Transformations

We study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik, Freie Universität Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph with n vertices in a grid of size bounded by W×H, where $W\leq\lfloor\frac{2n-2}{3}\rfloorWe study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik, Freie Universit?t Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph with n vertices in a grid of size bounded by W×H, where W ￡ ?\frac2n-23?W\leq\lfloor\frac{2n-2}{3}\rfloor , and W+H ￡ ?\frac4n-43?W+H\leq\lfloor \frac{4n-4}{3}\rfloor . It uses at most ?\frac2n-53?\lfloor\frac{2n-5}{3}\rfloor bends, and each edge uses at most one bend. Our algorithm is area optimal. Compared with the existing area optimal polyline drawing algorithm proposed in Bonichon et al. (Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 2573, pp. 35–46, Springer, Berlin, 2002), our algorithm uses a smaller number of bends. Their bend bound is (n−2).     

Simulation of simultaneous safe recursion over an arbitrary structure

In [O. Bournez, F. Cucker, P.J. de Naurois, J.Y. Marion, Computability over an arbitrary structure. Sequential and parallel polynomial time, in: Lecture Notes in Computer Science, vol. 2620, Springer, Berlin, 2003, pp. 185-199] the class of safe recursive functions over an arbitrary structure is defined. A question of simulation of the simultaneous safe recursion by single safe recursion was set. We prove that this simulation is feasible using bounded coding and decoding functions.     

A Novel Stochastic Game Via the Quantitative μ-calculus

The quantitative μ-calculus qMμ extends the applicability of Kozen's standard μ-calculus [D. Kozen, Results on the propositional μ-calculus, Theoretical Computer Science 27 (1983) 333–354] to probabilistic systems. Subsequent to its introduction [C. Morgan, and A. McIver, A probabilistic temporal calculus based on expectations, in: L. Groves and S. Reeves, editors, Proc. Formal Methods Pacific '97 (1997), available at [PSG, Probabilistic Systems Group: Collected reports, http://web.comlab.ox.ac.uk/oucl/research/areas/probs/bibliography.html]; also appears at [A. McIver, and C. Morgan, “Abstraction, Refinement and Proof for Probabilistic Systems,” Technical Monographs in Computer Science, Springer, New York, 2005, Chap. 9], M. Huth, and M. Kwiatkowska, Quantitative analysis and model checking, in: Proceedings of 12th annual IEEE Symposium on Logic in Computer Science, 1997] it has been developed by us [A. McIver, and C. Morgan, Games, probability and the quantitative μ-calculus qMu, in: Proc. LPAR, LNAI 2514 (2002), pp. 292–310, revised and expanded at [A. McIver, and C. Morgan, Results on the quantitative μ-calculus qMμ (2005), to appear in ACM TOCL]; also appears at [A. McIver, and C. Morgan, “Abstraction, Refinement and Proof for Probabilistic Systems,” Technical Monographs in Computer Science, Springer, New York, 2005, Chap. 11], A. McIver, and C. Morgan, “Abstraction, Refinement and Proof for Probabilistic Systems,” Technical Monographs in Computer Science, Springer, New York, 2005, A. McIver, and C. Morgan, Results on the quantitative μ-calculus qMμ (2005), to appear in ACM TOCL] and by others [L. de Alfaro, and R. Majumdar, Quantitative solution of omega-regular games, Journal of Computer and System Sciences 68 (2004) 374–397]. Beyond its natural application to define probabilistic temporal logic [C. Morgan, and A. McIver, An expectation-based model for probabilistic temporal logic, Logic Journal of the IGPL 7 (1999), pp. 779–804, also appears at [A. McIver, and C. Morgan, “Abstraction, Refinement and Proof for Probabilistic Systems,” Technical Monographs in Computer Science, Springer, New York, 2005, Chap.10]], there are a number of other areas that benefit from its use.One application is stochastic two-player games, and the contribution of this paper is to depart from the usual notion of “absolute winning conditions” and to introduce a novel game in which players can “draw”.The extension is motivated by examples based on economic games: we propose an extension to qMμ so that they can be specified; we show that the extension can be expressed via a reduction to the original logic; and, via that reduction, we prove that the players can play optimally in the extended game using memoryless strategies.     

Expand,Enlarge and Check: New algorithms for the coverability problem of WSTS

In this paper, we present a general algorithmic schema called ‘Expand, Enlarge and Check’ from which new algorithms for the coverability problem of WSTS can be constructed. We show here that our schema allows us to define forward algorithms that decide the coverability problem for several classes of systems for which the Karp and Miller procedure cannot be generalized, and for which no complete forward algorithms were known. Our results have important applications for the verification of parameterized systems and communication protocols.A preliminary version of this paper has been published as [Geeraerts et al., Expand, enlarge and check: new algorithms for the coverability problem of WSTS, in: Proceedings of the 24th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 04), Lecture Notes in Computer Science, vol. 3328, Springer, Berlin, 2004, pp. 287–298] in the proceedings of FST&TCS 2004.     

Tangential cover for thick digital curves

The recognition of digital shapes is a deeply studied problem. The arithmetical framework, initiated by Reveillès [Géométrie discrète, calcul en nombres entiers et algorithmique, Thèse d’Etat, 1991], provides a powerful theoretical basis, as well as many algorithms to deal with digital objects. The tangential cover, first presented in Feschet and Tougne [Optimal time computation of the tangent of a discrete curve: application to the curvature, in: G. Bertrand, M. Couprie, L. Perroton (Eds.), 8th Discrete Geometry for Computer Imagery, Lecture Notes in Computer Science, vol. 1568, Springer, Berlin, 1999, pp. 31-40] and Feschet [Canonical representations of discrete curves, Pattern Anal. Appl. 8(1-2) (2005) 84-94] is a useful tool for representing geometric digital primitives. It computes the set of all maximal segments of a digital curve and permits either to obtain minimal length polygonalization or asymptotic convergence of tangents estimations. Nevertheless, the arithmetical approach does not tolerate the introduction of irregularities, which are however inherent to the acquisition of digital shapes. The present paper is an extension of Faure and Feschet [Tangential cover for thick digital curves, in: D. Coeurjolly, I. Sivignon, L. Tougne, F. Dupont (Eds.), DGCI 2008, Lecture Notes in Computer Science, vol. 4992, Springer, Berlin, 2008, pp. 358-369], in which we propose a new definition for a class of the so-called “thick digital curves” that applies well to a large class of digital object boundaries. We then propose an extension of the tangential cover to thick digital curves and provide an algorithm with an O(nlogn) time complexity, where n denotes the number of points of specific subparts of the thick digital curve. In order to keep up with this low complexity, some critical points must be taken into account. We describe all required implementation details in this paper.     

Conformal Geometric Algebra for Robotic Vision

In this paper the authors introduce the conformal geometric algebra in the field of visually guided robotics. This mathematical system keeps our intuitions and insight of the geometry of the problem at hand and it helps us to reduce considerably the computational burden of the problems. As opposite to the standard projective geometry, in conformal geometric algebra we can deal simultaneously with incidence algebra operations (meet and join) and conformal transformations represented effectively using spinors. In this regard, this framework appears promising for dealing with kinematics, dynamics and projective geometry problems without the need to resort to different mathematical systems (as most current approaches do). This paper presents real tasks of perception and action, treated in a very elegant and efficient way: body–eye calibration, 3D reconstruction and robot navigation, the computation of 3D kinematics of a robot arm in terms of spheres, visually guided 3D object grasping making use of the directed distance and intersections of lines, planes and spheres both involving conformal transformations. We strongly believe that the framework of conformal geometric algebra can be, in general, of great advantage for applications using stereo vision, range data, laser, omnidirectional and odometry based systems. Eduardo Jose Bayro-Corrochano gained his Ph.D. in Cognitive Computer Science in 1993 from the University of Wales at Cardiff. From 1995 to 1999 he has been Researcher and Lecturer at the Institute for Computer Science, Christian Albrechts University, Kiel, Germany, working on applications of geometric Clifford algebra to cognitive systems.  His current research interest focuses on geometric methods for artificial perception and action systems. It includes geometric neural networks, visually guidevsd robotics, color image processing, Lie bivector algebras for early vision and robot maneuvering. He is editor and author of the following books: Geometric Computing for Perception Action Systems, E. Bayro-Corrochano, Springer Verlag, 2001; Geometric Algebra with Applications in Science and Engineering, E. Bayro-Corrochano and G. Sobczyk (Eds.), Birkahauser 2001; Handbook of Computational Geometry for Pattern Recognition, Computer Vision, Neurocomputing and Robotics, E. Bayro-Corrochano, Springer Verlag, 2005. He authored more than 90 strictly reviewed papers. Leo Hendrick Reyes-Lozano received his degree in Computer Engineering from the University of Guadalajara in 1999. He earned his MSc. and Ph.D. from the Center of Research and Advanced Studies (CINVESTAV) Guadalajara in 2001 and 2004, respectively. His research interests include Computer Vision, Geometric Algebra and Computer Graphics. Julio Zamora-Esquivel received his degree in Electronic Engineering at the Guzman City Institute of Tecnology in 2000. He earned his MSc. at the Center of Research and Advanced Studies (CINVESTAV) in Guadalajara in 2003. He is currently a Ph.D Candidate at CINVESTAV. His research interests include Computer Vision, Geometric Algebra and Robotics.     

A note on weighted distributed match-making

In many distributed computing environments, processes are concurrently executed by nodes in a store-and-forward network. Distributed control issues as diverse as name-server, mutual exclusion, and replicated data management, involve making matches between processes. The generic paradigm is a formal problem called “distributed match-making.” We define multidimensional and weighted versions, and the relations between the two, and develop a very general method to prove lower bounds on the complexity as a tradeoff between number of messages and “distributedness.” The resulting lower bounds are tight in all cases we have examined. We present a success-stop version of distributed match-making that is analysed in terms of a weight distribution that in all cases results in approximately halving the (expected) number of messages required in the corresponding strategy that does not use these weights. The second author did part of this work at the Laboratory for Computer Science, M.I.T., Cambridge, MA. He was supported in part by the Office of Naval Research under Contract N00014-85-K-0168, by the Office of Army Research under Contract DAAG29-84-K-0058, by the National Science Foundation under Grant DCR-83-02391, and by the Defence Advanced Research Projects Agency (DARPA) under Contract N00014-83-K-0125. A preliminary version of this paper appeared inProc. VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing (AWOC 88), Lecture Notes in Computer Science, vol. 319, Springer-Verlag, Berlin, 1988, pp. 361–368.     

Adaptive thresholding of tomograms by projection distance minimization

Segmentation is an important step to obtain quantitative information from tomographic data sets. However, it is usually not possible to obtain an accurate segmentation based on a single, global threshold. Instead, local thresholding schemes can be applied that use a varying threshold. Selecting the best local thresholds is not a straightforward task, as local image features often do not provide sufficient information for choosing a proper threshold.Recently, the concept of projection distance was proposed by the authors as a new criterion for evaluating the quality of a tomogram segmentation [K.J. Batenburg, J. Sijbers, Automatic threshold selection for tomogram segmentation by reprojection of the reconstructed image, in: Computer Analysis of Images and Patterns, in: Lecture Notes in Computer Science, vol. 4673, Springer, Berlin/Heidelberg, 2007, pp. 563-570.]. In this paper, we describe how projection distance minimization (PDM) can be used to select local thresholds, based on the available projection data from which the tomogram was initially computed.The results of several experiments are presented in which our local thresholding approach is compared with alternative thresholding methods. These results demonstrate that the local thresholding approach yields segmentations that are significantly more accurate compared to previously published methods, in particular when the initial reconstruction contains artifacts.     

Infinite Computations and a Hierarchy in {Delta}3 Reconsidered

In this note, we reconsider the results in Rovan and Steskal(2007, Vol. 4497 of Lecture Notes in Computer Science, pp. 660–669,Springer) concerning TMDC (Display Turing Machines with Control)with Chomsky like control language. We shall show that, underthe given assumptions, various degrees of the control complexitydo not give rise to a hierarchy of language families, thus correctingan error in Rovan and Steskal (2007, Vol. 4497 of Lecture Notesin Computer Science, pp. 660–669, Springer).     

Weighted tree automata and weighted logics

We define a weighted monadic second order logic for trees where the weights are taken from a commutative semiring. We prove that a restricted version of this logic characterizes the class of formal tree series which are accepted by weighted bottom-up finite state tree automata. The restriction on the logic can be dropped if additionally the semiring is locally finite. This generalizes corresponding classical results of Thatcher, Wright, and Doner for tree languages and it extends recent results of Droste and Gastin [Weighted automata and weighted logics, in: Automata, Languages and Programming—32nd International Colloquium, ICALP 2005, Lisbon, Portugal, 2005, Proceedings, Lecture Notes in Computer Science, Vol. 3580, Springer, Berlin, 2005, pp. 513–525, full version in Theoretical Computer Science, to appear.] from formal power series on words to formal tree series.     

Hierarchical deablock detection for nested transactions

In this paper, we propose an algorithm for detecting deadlocks in a distributed Nested Transaction. This algorthms does not require that the global wait-for graph be built and maintained nor that the edges of a global wait-for graph be followed in order for deadlocks to be detected. Our algorithm uses the fact that transactions are organized in a tree structure. Each transaction maintains a representative wait-for graph that summarizes the waiting conditions in the subtree below the transaction. Deadlocks can be detected by individually checking these condensed wait-for graph. Marta Rukoz received an under-graduate degree in Computer Science from the Central University of Venezuela in 1981, a Masters degree from Simon Bolivar University in 1985, and a Ph.D. from the Pierre et Marie Curie, Paris VI University in France. She was a member of the faculty at the Central University of Venezuela from 1982–1985 and returned in 1989 where she is currently a Professor Agregado. From 1987–1989 she worked at the University of Paris Nord. Professor Rukoz's research interests include: distributed algorithms, distributed databases, and Petri net models.A preliminary draft of this paper appears in Bermond J, Raynal M (eds) Proceedings of distributed algorithms. Lect Notes Comput Sci. vol. 392. Springer, Berlin Heidelberg New York, 1989     

CSP-CASL—A new integration of process algebra and algebraic specification

CSP–CASL integrates the process algebra CSP [T. Hoare, Communicating Sequential Processes, Prentice-Hall, Englewood cliffs, NJ, 1985; A.W. Roscoe, The Theory and Practice of Concurrency, Prentice-Hall, Englewood cliffs, NJ, 1998] with the algebraic specification language CASL [P.D. Mosses (Ed.), CASL Reference Manual, Lecture Notes in Computer Science, Vol. 2960, Springer, Berlin, 2004; E. Astesiano, M. Bidoit, B. Krieg-Brückner, H. Kirchner, P.D. Mosses, D. Sannella, A. Tarlecki, CASL—the common algebraic specification language, Theoret. Comput. Sci. 286 (2002) 153–196]. Its novel aspects include the combination of denotational semantics in the process part and, in particular, loose semantics for the data types covering both concepts of partiality and sub-sorting. Technically, this integration involves the development of a new so-called data-logic formulated as an institution. This data-logic serves as a link between the institution underlying CASL and the alphabet of communications necessary for the CSP semantics. Besides being generic in the various denotational CSP semantics, this construction leads also to an appropriate notion of refinement with clear relations to both data refinement in CASL and process refinement in CSP.     

On general construction for extended visual cryptography schemes

Numerous visual cryptography schemes (VCSs) have been proposed to protect a secret image with share images. Most VCSs use random-looking shares to code a single binary secret image. Some schemes are designed for color secret images. Droste's [New results on visual cryptography, in: Advances in Cryptology-CRYPTO ’96, Lecture Notes in Computer Science, vol. 1109, Springer, Berlin, 1996, pp. 401-415] (n,n)-VCS is introduced for multiple binary secret images. Extended VCS (EVCS), by Ateniese et al. [Extended capabilities for visual cryptography, Theoretical Computer Science 250 (2001) 143-161], for binary secret image uses meaningful (innocent-looking) shares. In this paper, we start with a more concise derivation of matrix extension in the ECVS model. This is implemented by concatenating an extended matrix to each basis matrix. We then present a general construction method for single or multiple binary/grayscale/color secret images using matrix extension utilizing meaningful shares. The result (k,n)-visual secret sharing schemes are more general than most existing schemes in terms of the secret/share image types. Using our matrix extension algorithm, any existing VCS with random-looking shares can be easily modified to utilize meaningful shares. The effectiveness of our schemes is demonstrated by real examples.     

On institutions for modular coalgebraic specifications

We present an algebraic extension of standard coalgebraic specification techniques for state-based systems which allows us to integrate constants and n-ary operations in a smooth way and which leads to institutions enabling the use of modular specification techniques. A sound and complete proof system for first-order observational properties of modular specifications is given. The framework of (Ω,Ξ)-structures that we present can be considered as the result of a transformation of concepts of observational logic as in Hennicker and Bidoit (in: A. Haeberer (Ed.), Algebraic Methodology and Software Technology (AMAST’98), Lecture Notes in Computer Science, vol. 1548, Springer, Berlin, 1999) into the coalgebraic world. Moreover, it is shown that the features of (Ω,Ξ)-structures that make them suitable models for an observational approach to specifications can be categorically expressed by the fact that the operation mapping an (Ω,Ξ)-structure to its behaviour is a fibred idempotent monad.     

Two impossibility theorems on behaviour specification of abstract data types

Two kinds of finite specification of the behaviour of a counter data type are proved impossible.We consider the class of data types (many-sorted algebras) behaving like an encapsulated counter that can be observed only by a test for zero. It is shown that no nonempty subclass of this class can be finitely specified in observational first-order logic, which is a variant of first-order logic in which equality may not be used on encapsulated types. Secondly, it is shown that the class cannot be described exactly by a finite specification in first-order logic.An extended abstract of a part of this paper appeared as: Schoett, O.: An observational subset of first-order logic cannot speacify the behaviour of a counter, in: Choffrut, C., Jantzen, M. (eds) STACS 91. 8th Annual Symposium on Theoretical Aspects of Computer Science (Lect. Notes comput. Sci., vol. 480, pp. 499–510) Berlin Heidelberg New York: Springer 1991     

Lie Algebra and System Identification Techniques for 3D Rigid Motion Estimation and Monocular Tracking

This paper addresses the parameters’ estimation of 2D and 3D transformations. For the estimation we present a method based on system identification theory, we named it the “A-method”. The transformations are considered as elements of the Lie group GL(n) or one of its subgroups. We represent the transformations in terms of their Lie Algebra elements. The Lie algebra approach assures to follow the shortest path or geodesic in the involved Lie group. To prove the potencial of our method, two experiments are presented. The first one is a monocular estimation of 3D rigid motion of an object in the visual space. With this aim, the six parameters of the rigid motion are estimated based on measurements of the six parameters of the affine transformation in the image. Secondly, we present the estimation of the affine or projective transformations involved in monocular region tracking. Jaime Ortegón-Aguilar received his degree in computer sciences at the Universidad Autonoma de Yucatan in Merida, Mexico in 2000. He earned his M.Sc. degree at the Cinvestav in Guadalajara, Mexico in 2002. He received his PhD degree from Cinvestav in 2006. His research interests include image processing, computer vision, robotics and applications of geometric algebra. Eduardo Jose Bayro-Corrochano gained his Ph.D. in Cognitive Computer Science in 1993 from the University of Wales at Cardiff. From 1995 to 1999 he has been Researcher and Lecturer at the Institute for Computer Science, Christian Albrechts University, Kiel, Germany, working on applications of geometric Clifford algebra to cognitive systems. At present is a full professor at CINVESTAV Unidad Guadalajara, México, Department of Electrical Engineering and Computer Science. His current research interest focuses on geometric methods for artificial perception and action systems. It includes geometric neural networks, visually guided robotics, humanoids, color image processing, Lie bivector algebras for early vision and robot maneuvering. He developed the quaternion wavelet transform for quaternion multi-resolution analysis using the phase concept. He is associate editor of Robotics and Journal of Advanced Robotic Systems and member of the editorial board of Journal of Pattern Recognition, Journal of Mathematical Imaging and Vision, Iberoamerican Journal of Computer and Systems and Journal of Theoretical and Numerical Approximation. He is editor and author of the following books: Geometric Computing for Perception Action Systems, E. Bayro-Corrochano, Springer Verlag, 2001; Geometric Algebra with Applications in Science and Engineering, E. Bayro-Corrochano and G. Sobczyk (Eds.), Birkhauser 2001; Handbook of Geometric Computing for Pattern Recognition, Computer Vision, Neurocomputing and Robotics, E. Bayro-Corrochano, Springer Verlag, 2005. He has published over 120 refereed journal, book chapters and conference papers. He is fellow of the IAPR society.     

The Theory and Use of the Quaternion Wavelet Transform

This paper presents the theory and practicalities of the quaternion wavelet transform (QWT). The major contribution of this work is that it generalizes the real and complex wavelet transforms and derives a quaternionic wavelet pyramid for multi-resolution analysis using the quaternionic phase concept. As a illustration we present an application of the discrete QWT for optical flow estimation. For the estimation of motion through different resolution levels we use a similarity distance evaluated by means of the quaternionic phase concept and a confidence mask. We show that this linear approach is amenable to be extended to a kind of quadratic interpolation. Eduardo Jose Bayro-Corrochano gained his Ph.D. in Cognitive Computer Science in 1993 from the University of Wales at Cardiff. From 1995 to 1999 he has been Researcher and Lecturer at the Institute for Computer Science, Christian Albrechts University, Kiel, Germany, working on applications of geometric Clifford algebra to cognitive systems. His current research interest focuses on geometric methods for artificial perception and action systems. It includes geometric neural networks, visually guidevsd robotics, color image processing, Lie bivector algebras for early vision and robot maneuvering. He is editor and author of the following books: Geometric Computing for Perception Action Systems, E. Bayro-Corrochano, Springer Verlag, 2001; Geometric Algebra with Applications in Science and Engineering, E. Bayro-Corrochano and G. Sobczyk (Eds.), Birkahauser 2001; Handbook of Computational Geometry for Pattern Recognition, Computer Vision, Neurocomputing and Robotics, E. Bayro-Corrochano, Springer Verlag, 2005.     

Playing with Conway’s problem

The centralizer of a language is the maximal language commuting with it. The question, raised by Conway in [J.H. Conway, Regular Algebra and Finite Machines, Chapman Hall, 1971], whether the centralizer of a rational language is always rational, recently received a lot of attention. In Kunc [M. Kunc, The power of commuting with finite sets of words, in: Proc. of STACS 2005, in: LNCS, vol. 3404, Springer, 2005, pp. 569–580], a strong negative answer to this problem was given by showing that even complete co-recursively enumerable centralizers exist for finite languages. Using a combinatorial game approach, we give here an incremental construction of rational languages embedding any recursive computation in their centralizers.     

Insight in discrete geometry and computational content of a discrete model of the continuum

This article presents a synthetic and self contained presentation of the discrete model of the continuum introduced by Harthong and Reeb [J. Harthong, Éléments pour une théorie du continu, Astérisque 109/110 (1983) 235-244.[1]; J. Harthong, Une théorie du continu, in: H. Barreau, J. Harthong (Eds.), La mathématiques non standard, Éditions du CNRS, 1989, pp. 307-329.[2]] and the related arithmetization process which led Reveillès [J.-P. Reveillès, Géométrie discrète, calcul en nombres entiers et algorithmique, Ph.D. Thesis, Université Louis Pasteur, Strasbourg, France, 1991.[3]; J.-P. Reveillès, D. Richard, Back and forth between continuous and discrete for the working computer scientist, Annals of Mathematics and Artificial Intelligence, Mathematics and Informatic 16(1-4) (1996) 89-152.[4]] to the definition of a discrete analytic line. We present then some basis on constructive mathematics [E. Bishop, D. Bridges, Constructive Analysis, Springer, Berlin, 1985.[5]], its link with programming [P. Martin-Löf, Constructive mathematics and computer programming, in: Logic, Methodology and Philosophy of Science, vol. VI, 1980, pp. 153-175.[6]; W.A. Howard, The formulae-as-types notion of construction, To H.B. Curry: Essays on Combinatory Logic, Lambda-calculus and Formalism, 1980, pp. 479-490.[7]] and we propose an analysis of the computational content of the so-called Harthong-Reeb line. More precisely, we show that a suitable version of this new model of the continuum partly fits with the constructive axiomatic of R proposed by Bridges [Constructive mathematics: a foundation for computable analysis, Theoretical Computer Science 219(1-2) (1999) 95-109.[8]]. This is the first step of a more general program on a constructive approach of the scaling transformation from discrete to continuous space.