The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Résumé Nous étudions le comportement des automates boustrophedon (automates finis lisant dans les deux sens) sur des mots infinis ou bi-infinis. Nous montrons (de façon effective) qu'un automate boustrophedon ne fait jamais mieux qu'un automate fini. En fait les parties de Aℕ ou Aℤ reconnues par lest boustrophedon sont exactement celles qui sont reconnues par les automates finis, sauf peut-être dans...
We present a model of a deterministic asynchronous input/output device based on functions between sets of labelled posets. For a restricted class of these, it is possible to reformulate the model in terms of partial functions between monoids from which we obtain an extension of the conventional sequential automaton. We conclude with some remarks on extensions to this work and its relationship to other...
Regular trees can be defined by two types of rational expressions, For these two types we solve the star-height problem i.e. we show how to construct a rational expression of minimal star-height from the minimal graph of the given tree (i.e. the analogous of the minimal deterministic automaton for regular langages). In one case, the minimal star-height is the rank (in the sense of Eggan) of the minimal...
We introduce yield of infinite trees. Trees are provided with usual syntactic order, words with a new order that canonically makes concatenation continuous. "Yield" operation is continuous. Our main result consists in the decidability of yield's equality for infinite regular trees.
The problem of characterizing the topological spaces that arise as adherences of languages of specified types is raised and pertinent concepts of general topology are reviewed. It is observed that the spaces that arise as adherences of arbitrary languages may be characterized as either: (1) the closed subsets of the Cantor ternary set; (2) the zero-dimensional compact metrizable spaces; or (3) the...
A word is called kth power-free if none of its non-empty factors have the form uk. A morphism is a kth power-free morphism it is preserves the kth power-free words. We present some conditions for some particular morphisms to be kth power-free. As a matter of fact we claim that the framework of the theory of codes is a good framework for these problems and we try to illustrate this.
We define sets of infinite words generated by various classes of iterated mappings. We show that every infinite word generated by an extended tag system can also be generated by an ε-free tag system. We give a full inclusion graph and several closure properties for the sets of infinite words considered. We investigate some extensions of tag systems using iterated sequential mappings.
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.