Automata and the arithmetic of formal power series
Automata, Borel functions and real numbers in Pisot base
This note is about functions ƒ : Aω → Bω whose graph is recognized by a Büchi finite automaton on the product alphabet A x B. These functions are Baire class 2 in the Baire hierarchy of Borel functions and it is decidable whether such function are continuous or not. In 1920 W. Sierpinski showed that a function is Baire class 1 if and only if both the overgraph and the undergraph of f are Fσ. We show that such characterization is also true for functions on infinite words if we replace the real...
Automata with modulo counters and nondeterministic counter bounds
We introduce and investigate Nondeterministically Bounded Modulo Counter Automata (NBMCA), which are two-way multi-head automata that comprise a constant number of modulo counters, where the counter bounds are nondeterministically guessed, and this is the only element of nondeterminism. NBMCA are tailored to recognising those languages that are characterised by the existence of a specific factorisation of their words, e. g., pattern languages. In this work, we subject NBMCA to a theoretically sound...
Automata with two-sided pushdowns defined over free groups generated by reduced alphabets
This paper introduces and discusses a modification of pushdown automata. This modification is based on two-sided pushdowns into which symbols are pushed from both ends. These pushdowns are defined over free groups, not free monoids, and they can be shortened only by the standard group reduction. We demonstrate that these automata characterize the family of recursively enumerable languages even if the free groups are generated by no more than four symbols.
Automata-based representations for infinite graphs
New compact representations of infinite graphs are investigated. Finite automata are used to represent labelled hyper-graphs which can be also multi-graphs. Our approach consists of a general framework where vertices are represented by a regular prefix-free language and edges are represented by a regular language and a function over tuples. We consider three different functions over tuples: given a tuple the first function returns its first difference, the second one returns its suffix and the last...
Automata-based Representations for Infinite Graphs
New compact representations of infinite graphs are investigated. Finite automata are used to represent labelled hyper-graphs which can be also multi-graphs. Our approach consists of a general framework where vertices are represented by a regular prefix-free language and edges are represented by a regular language and a function over tuples. We consider three different functions over tuples: given a tuple the first function returns its first difference, the second one returns its suffix and...
Automated Processing of TeX-Typeset Articles for a Digital Library
Experience in setting up a comprehensive journal processing system based on the TeX typesetting system with the CEDRAM workflow is described, following the example of the Archivum Mathematicum journal. The system automates the preparation of issues and simultaneously generates the materials needed for the Czech Digital Mathematics Library project (DML-CZ). The second part of the article describes the process of transformation of archival born-digital articles into a DML-CZ-suitable format.
Automated proofs for some Stirling number identities.
Automated proofs of upper bounds on the running time of splitting algorithms.
Automated theorem proving in monadic predicate calculus
Automates boustrophedon, semi-groupe de Birget et monoïde inversif libre
Automates calculant la complexité de suites automatiques
Le point fixe d’une substitution injective uniforme de module sur un alphabet est examiné du point de vue du nombre de ses blocs distincts de longueur . Lorsque est minimal et de cardinal deux, nous construisons un automate pour la suite .
Automates de coût borné sur un alphabet à une lettre
Automates et algébricités
Dans quelle mesure la régularité des chiffres d’un nombre réel dans une base entière, celle des quotients partiels du développement en fraction continuée d’un nombre réel, ou celle des coefficients d’une série formelle sont-elles liées à l’algébricité ou à la transcendance de ce réel ou de cette série formelle ? Nous proposons un survol de résultats récents dans le cas où la régularité évoquée ci-dessus est celle de suites automatiques, substitutives, ou sturmiennes.
Automates et codes zigzag
Automates et commutations partielles
Automates et fractions continues
Automates et langages
Automates et valeurs de transcendance du logarithme de Carlitz
Automates finis