36 research outputs found
Pascal Marsault, órgano (Francia) y Collectiv Cuivres, quinteto de cobres (Francia)
No full textConcierto interpretado por Pascal Marsault (Francia)y el quinteto de metales Collectiv Ciuvres en el marco del Segundo Festival de Órgano. Este año se realiza la segunda versión del festival, el cual incluye una conferencia, dos conversatorios y tres conciertos, además de la sexta versión del curso.
En este concierto interpretaron obras de Claudio Monteverdi, Johann Sebastian Bach, Hieronymus Praetorius, Anton Bruckner, Georg Friederlc Haendel, Alexandre Guilmant, Diego Vega, Albert Renaud, Victor Ewald, Franz Liszt y Nikolai Rimsky-Korsakov
On p/q-recognisable sets
No full textInternational audienceLet p/q be a rational number. Numeration in base p/q is defined by a function that evaluates each finite word over A_p={0,1,...,p-1} to some rational number. We let N_p/q denote the image of this evaluation function. In particular, N_p/q contains all nonnegative integers and the literature on base p/q usually focuses on the set of words that are evaluated to nonnegative integers; it is a rather chaotic language which is not context-free. On the contrary, we study here the subsets of (N_p/q)^d that are p/q-recognisable, i.e. realised by finite automata over (A_p)^d. First, we give a characterisation of these sets as those definable in a first-order logic, similar to the one given by the B\"uchi-Bruy\`ere Theorem for integer bases numeration systems. Second, we show that the natural order relation and the modulo-q operator are not p/q-recognisable
An efficient algorithm to decide periodicity of -recognisable sets using LSDF convention
No full textInternational audienceLet be an integer strictly greater than . Each set of nonnegative integers is represented in base by a language over . The set is said to be -recognisable if it is represented by a regular language. It is known that ultimately periodic sets are -recognisable, for every base , and Cobham's theorem implies the converse: no other set is -recognisable in every base . We consider the following decision problem: let be a set of nonnegative integers that is -recognisable, given as a finite automaton over , is periodic? Honkala showed in 1986 that this problem is decidable. Later on, Leroux used in 2005 the convention to write number representations with the least significant digit first (LSDF), and designed a quadratic algorithm to solve a more general problem. We use here LSDF convention as well and give a structural description of the minimal automata that accept periodic sets. Then, we show that it can be verified in linear time if a minimal automaton meets this description. In general, this yields a procedure to decide whether an automaton with states accepts an ultimately periodic set of nonnegative integers
An efficient algorithm to decide periodicity of b-recognisable sets using MSDF convention
No full textpeer reviewedGiven an integer base b>1, a set of integers is represented in base b by a language over {0,1,...,b-1}. The set is said to be b-recognisable if its representation is a regular language. It is known that eventually periodic sets are b-recognisable in every base b, and Cobham's theorem implies the converse: no other set is b-recognisable in every base b.
We are interested in deciding whether a -recognisable set of integers (given as a finite automaton) is eventually periodic. Honkala showed that this problem is decidable in 1986 and recent developments give efficient decision algorithms. However, they only work when the integers are written with the least significant digit first.
In this work, we consider the natural order of digits (Most Significant Digit First) and give a quasi-linear algorithm to solve the problem in this case
Matching walks that are minimal with respect to edge inclusion
No full text15 pages, 5 figuresIn this paper we show that enumerating the set MM(G,R), defined below, cannot be done with polynomial-delay in its input G and R, unless P=NP. R is a regular expression over an alphabet , G is directed graph labeled over , and MM(G,R) contains walks of G. First, consider the set Match(G,R) containing all walks G labeled by a word (over ) that conforms to . In general, M(G,R) is infinite, and MM(G,R) is the finite subset of Match(G,R) of the walks that are minimal according to a well-quasi-order <. It holds
Matching walks that are minimal with respect to edge inclusion
No full text15 pages, 5 figuresIn this paper we show that enumerating the set MM(G,R), defined below, cannot be done with polynomial-delay in its input G and R, unless P=NP. R is a regular expression over an alphabet , G is directed graph labeled over , and MM(G,R) contains walks of G. First, consider the set Match(G,R) containing all walks G labeled by a word (over ) that conforms to . In general, M(G,R) is infinite, and MM(G,R) is the finite subset of Match(G,R) of the walks that are minimal according to a well-quasi-order <. It holds
Énumération et numération
No full textThis memoir involves several domains of discrete mathematics and theoretical computer science, such as formal languages, numeration, combinatorics on words, algorithmic, complexity, etc. In summary, various problems, all from the general area of numeration, are addressed by means of automata and transducers theory. We first consider integer base numeration systems. Given as a parameter an integer base b, we give a quasi-linear and structural algorithm to decide whether the language accepted by a given automaton is the set of the representations (in base b) of an ultimately periodic set of integers.Second, we consider the rational base p/q and particularly the language L_p/q of the representations of integers in this base. It is a quite complex language according to the usual criteria: in particular, it has a property called FLIP (for Finite Left Iteration Property) which implies that L_p/q does not satisfies any kind of pumping lemma. We prove that, if a monoid M is finitely generated and contains only numbers that are representable in base p/q, then the language of all the representations of the numbers of M possesses the FLIP property. We then study L_p/q from a different perspective: with every integer is associated an infinite word called minimal and we consider the function that maps the minimal word associated with n to the minimal word associated with (n+1); we show that this function is realised by an infinite transducer whose structure is virtually the same as the one of L_p/q. We finally describe a way to serialise a infinite tree and language into an infinite word, called signatures, by means of a breadth-first traversal. We first note that the signatures of regular languages form a subclass of morphic words, a result linked to the classical transformation automaton/word morphism. We then treat the case of periodic signatures and show their intrinsic relationship with rational base numeration systems: for every base p/q the language L_p/q has a periodic signature; given a finite sequence r of integer (that we call rhythm) the signature r^ω generates a language that is a non-canonical way to represent the set of all integers in base p/q, where p/q is the average of components of r. The notion of signature allows us to define an automaton transformation, called surminimisation, that reduces the number of states of the input automaton, more so than a classical minimisation. However, whereas an automaton and its minimisation accept the same language, it is in general not the case for an automaton and its surminimisation: the surminimisation process indeed preserves only the underlying ordered tree.Ce mémoire aborde et résout des problèmes assez différents, ayant tous trait à la numération, avec une certaine unité conceptuelle quant aux moyens mis en œuvre pour les résoudre: la théorie des automates. Nous considérons d'abord les bases entières et présentons un algorithme quasi-linéaire et structurel permettant de décider si le langage accepté par un automate donné est la représentation d'un ensemble ultimement périodique d'entiers. Ensuite, nous étudions la base rationnelle p/q et particulièrement le langage L_p/q des représentations des entiers dans cette base. Il s'agit d'un langage relativement complexe selon la théorie classique des langages formels : il ne satisfait aucune forme de lemme d’itération. Nous montrons que chaque monoïde finiment engendré est représenté par un langage aussi complexe que L_p/q. Nous prenons ensuite une perspective différente pour étudier L_p/q : à chaque entier est associé un mot infini, dit minimal, et l'on étudie la fonction qui associe le mot minimal d'un entier n à celui de son successeur (n+1) ; nous montrons en particulier que cette fonction est réalisée par un transducteur infini dont la structure est très proche de celle du langage L_p/q.Enfin, nous décrivons une manière de sérialiser les arbres infinis et les langages en des mots, appelés signatures, par le moyen d'un parcours en largeur. On remarque d'abord que les langages réguliers sont associés aux mots morphiques, ce qui rejoint le lien entre les systèmes de numération abstraits réguliers et les systèmes de numération morphiques (aussi dit de Dumont-Thomas). On traite ensuite le cas des signatures périodiques et l'on montre qu'elles sont liées aux bases rationnelles ; ceci donne également une procédure pour construire L_p/q de façon très simple. Enfin, nous définissons une transformation d'automate, la surminimisation, qui réduit le nombre d'états d'un automate au delà de ce que permet la minimisation classique ; en contrepartie, un automate et sa surminimisation n'acceptent pas le même langage, mais seulement des langages avec le même arbre ordonné sous-jacent
Énumération et numération
No full textThis memoir involves several domains of discrete mathematics and theoretical computer science, such as formal languages, numeration, combinatorics on words, algorithmic, complexity, etc. In summary, various problems, all from the general area of numeration, are addressed by means of automata and transducers theory. We first consider integer base numeration systems. Given as a parameter an integer base b, we give a quasi-linear and structural algorithm to decide whether the language accepted by a given automaton is the set of the representations (in base b) of an ultimately periodic set of integers.Second, we consider the rational base p/q and particularly the language L_p/q of the representations of integers in this base. It is a quite complex language according to the usual criteria: in particular, it has a property called FLIP (for Finite Left Iteration Property) which implies that L_p/q does not satisfies any kind of pumping lemma. We prove that, if a monoid M is finitely generated and contains only numbers that are representable in base p/q, then the language of all the representations of the numbers of M possesses the FLIP property. We then study L_p/q from a different perspective: with every integer is associated an infinite word called minimal and we consider the function that maps the minimal word associated with n to the minimal word associated with (n+1); we show that this function is realised by an infinite transducer whose structure is virtually the same as the one of L_p/q. We finally describe a way to serialise a infinite tree and language into an infinite word, called signatures, by means of a breadth-first traversal. We first note that the signatures of regular languages form a subclass of morphic words, a result linked to the classical transformation automaton/word morphism. We then treat the case of periodic signatures and show their intrinsic relationship with rational base numeration systems: for every base p/q the language L_p/q has a periodic signature; given a finite sequence r of integer (that we call rhythm) the signature r^ω generates a language that is a non-canonical way to represent the set of all integers in base p/q, where p/q is the average of components of r. The notion of signature allows us to define an automaton transformation, called surminimisation, that reduces the number of states of the input automaton, more so than a classical minimisation. However, whereas an automaton and its minimisation accept the same language, it is in general not the case for an automaton and its surminimisation: the surminimisation process indeed preserves only the underlying ordered tree.Ce mémoire aborde et résout des problèmes assez différents, ayant tous trait à la numération, avec une certaine unité conceptuelle quant aux moyens mis en œuvre pour les résoudre: la théorie des automates. Nous considérons d'abord les bases entières et présentons un algorithme quasi-linéaire et structurel permettant de décider si le langage accepté par un automate donné est la représentation d'un ensemble ultimement périodique d'entiers. Ensuite, nous étudions la base rationnelle p/q et particulièrement le langage L_p/q des représentations des entiers dans cette base. Il s'agit d'un langage relativement complexe selon la théorie classique des langages formels : il ne satisfait aucune forme de lemme d’itération. Nous montrons que chaque monoïde finiment engendré est représenté par un langage aussi complexe que L_p/q. Nous prenons ensuite une perspective différente pour étudier L_p/q : à chaque entier est associé un mot infini, dit minimal, et l'on étudie la fonction qui associe le mot minimal d'un entier n à celui de son successeur (n+1) ; nous montrons en particulier que cette fonction est réalisée par un transducteur infini dont la structure est très proche de celle du langage L_p/q.Enfin, nous décrivons une manière de sérialiser les arbres infinis et les langages en des mots, appelés signatures, par le moyen d'un parcours en largeur. On remarque d'abord que les langages réguliers sont associés aux mots morphiques, ce qui rejoint le lien entre les systèmes de numération abstraits réguliers et les systèmes de numération morphiques (aussi dit de Dumont-Thomas). On traite ensuite le cas des signatures périodiques et l'on montre qu'elles sont liées aux bases rationnelles ; ceci donne également une procédure pour construire L_p/q de façon très simple. Enfin, nous définissons une transformation d'automate, la surminimisation, qui réduit le nombre d'états d'un automate au delà de ce que permet la minimisation classique ; en contrepartie, un automate et sa surminimisation n'acceptent pas le même langage, mais seulement des langages avec le même arbre ordonné sous-jacent
