Afficher la notice abrégée

dc.contributor.advisorLombardy, Sylvain
dc.contributor.authorDANDO, Louis-Marie
dc.contributor.otherLombardy, Sylvain
dc.contributor.otherCaron, Pascal
dc.contributor.otherBéal, Marie-Pierre
dc.contributor.otherMuscholl, Anca
dc.date2019-09-09
dc.identifier.urihttp://www.theses.fr/2019BORD0130/abes
dc.identifier.uri
dc.identifier.urihttps://tel.archives-ouvertes.fr/tel-02350722
dc.identifier.nnt2019BORD0130
dc.description.abstractCette thèse porte sur certaines extensions des automates pondérés, et étudie les séries qu’ils réalisent en fonction de la nature des poids.Ces extensions se distinguent par les mouvements supplémentaires autorisés à la tête de lecture de l’automate : retour au début du mot pour les automates circulaires, changement de sens de lecture pour les automates boustrophédons.Dans le cas général, les automates pondérés circulaires sont plus puissants que les automates unidirectionnels classiques, et moins puissants que les boustrophédons.On introduit de plus les expressions de Hadamard, qui sont une extension des expressions rationnelles et qui permettent de dénoter le comportement des automates circulaires. Les aspects algorithmiques de cette conversion sont étudiés dans le cas où les poids appartiennent à un semi-anneau rationnellement additif.On montre que lorsque les poids sont des nombres rationnels, réels ou complexes, les automates circulaires sont aussi expressifs que les boustrophédons.Enfin, si les poids forment un bi-monoïde localement fini, les automates boustrophédons ne sont pas plus expressifs que les automates pondérés classsiques.
dc.description.abstractEnThis thesis deals with some extensions of weighted automata,and studies the series they can realisedepending on the nature of their weigths.These extensions are characterised by howthe input head of the automaton is allowed to move:rotating automata can go back at the beginning of the word,and two-way automata can change the reading direction.In the general setting, weigthed rotating automata are morepowerful than classical one-way automata, and less powerfulthan two-way ones.Moreover, we introduce Hadamard expressions,which are an extension of rational expressions and can denotethe behaviour of rotating automata.The algorithms for this conversion are studied when the weights belong toa rationally additive semiring.Then, rotating automata are shown as expressive as two-way automatain the case of rational, real or complex numbers.It is also proved that two-way and one-way automataare equivalent when weighted on a locally finite bimonoid.
dc.language.isofr
dc.subjectAutomates pondérés
dc.subjectThéorie algébrique des langages
dc.subjectAutomates circulaires
dc.subjectSéries rationnelles
dc.subjectAutomates boustrophédons
dc.subjectSéries de Hadamard
dc.subject.enWeighted automata
dc.subject.enAlgebraic language theory
dc.subject.enRotating automata
dc.subject.enRational series
dc.subject.enTwo-Way automata
dc.subject.enHadamard series
dc.titleExpressivité des automates pondérés circulaires et boustrophédons
dc.title.enExpressivity of weighted rotating and two-way automata
dc.typeThèses de doctorat
dc.contributor.jurypresidentTalbot, Jean-Marc
bordeaux.hal.laboratoriesLaboratoire bordelais de recherche en informatique
bordeaux.type.institutionBordeaux
bordeaux.thesis.disciplineInformatique
bordeaux.ecole.doctoraleÉcole doctorale de mathématiques et informatique (Talence, Gironde)
star.origin.linkhttps://www.theses.fr/2019BORD0130
dc.contributor.rapporteurCaron, Pascal
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Expressivit%C3%A9%20des%20automates%20pond%C3%A9r%C3%A9s%20circulaires%20et%20boustroph%C3%A9dons&rft.atitle=Expressivit%C3%A9%20des%20automates%20pond%C3%A9r%C3%A9s%20circulaires%20et%20boustroph%C3%A9dons&rft.au=DANDO,%20Louis-Marie&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée