京都大学 / 新制・課程博士 / 博士(情報学) / 甲第25423号 / 情博第861号 / 新制||情||144(附属図書館) / 京都大学大学院情報学研究科知能情報学専攻 / (主査)特定教授 黒橋 禎夫, 教授 河原 達也, 教授 西野 恒 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

We propose subword spotting, a generalization of word spotting where the search is for groups of characters within words. We present a method for performing subword spotting based on state-of-the-art word spotting techniques and evaluate its performance at three granularitires (unigrams, bigrams and trigrams) on two datasets. We demonstrate three applications of subword spotting, though others may exist. The first is assisting human transcribers identify unrecognized characters by locating them in other words. The second is searching for suffixes directly in word images (suffix spotting). And the third is computer assisted transcription (semi-automated transcription). We investigate several variations of computer assisted transcription using subword spotting, but none achieve transcription speeds above manual transcription. We investigate the causes.

We propose subword spotting, a generalization of word spotting where the search is for groups of characters within words. We present a method for performing subword spotting based on state-of-the-art word spotting techniques and evaluate its performance at three granularitires (unigrams, bigrams and trigrams) on two datasets.We demonstrate three applications of subword spotting, though others may exist. The first is assisting human transcribers identify unrecognized characters by locating them in other words. The second is searching for suffixes directly in word images (suffix spotting). And the third is computer assisted transcription (semi-automated transcription). We investigate several variations of computer assisted transcription using subword spotting, but none achieve transcription speeds above manual transcription. We investigate the causes.

As emerging portable multimedia applications demand more and more computational throughput with limited energy consumption, the need for high-efficiency, high-throughput embedded processing is becoming an important challenge in computer architecture. In this regard, this dissertation addresses application-, architecture-, and technology-level issues in existing processing systems to provide efficient processing of multimedia in many, or ideally all, of its form. In particular, this dissertation explores color imaging in multimedia while focusing on two architectural enhancements for memory- and performance-hungry embedded applications: (1) a pixel-truncation technique and (2) a color-aware instruction set (CAX) for embedded multimedia systems. The pixel-truncation technique differs from previous techniques (e.g., 4:2:2 and 4:2:0 subsampling) used in image and video compression applications (e.g., JPEG and MPEG) in that it reduces the information content in individual pixel word sizes rather than in each dimension. Thus, this technique drastically reduces the bandwidth and memory required to transport and store color images without perceivable distortion in color. At the same time, it maintains the pixel storage format of color image processing in which each pixel computation is performed simultaneously on 3-D YCbCr components, which are widely used in the image and video processing community. CAX supports parallel operations on two-packed 16-bit (6:5:5) YCbCr data in a 32-bit datapath processor, providing greater concurrency and efficiency for processing color image sequences. This dissertation presents the impact of CAX on processing performance and on both area and energy efficiency for color imaging applications in three major processor architectures: dynamically scheduled (superscalar), statically scheduled (very long instruction word, VLIW), and embedded single instruction multiple data (SIMD) array processors. Unlike typical multimedia extensions, CAX obtains substantial performance and code density improvements through direct support for color data processing rather than depending solely on generic subword parallelism. In addition, the ability to reduce data format size reduces system cost. The reduction in data bandwidth also simplifies system design. In summary, CAX, coupled with the pixel-truncation technique, provides an efficient mechanism that meets the computational requirements and cost goals for future embedded multimedia products.

<p>In the thesis we are concerned with actual problems on palindromic subwords and palindromic factors of finite and infinite words. The main course of the research are the ways of determining which of two given words is &ldquo;more palindromic&rdquo; than the other one, that is, defining a measure for the degree of &ldquo;palindromicity&rdquo; of a word. Particularly, we pay attention to two actual approaches: the so-called MP-ratio and the so-called <em>palindromic defect</em>, and answer several open questions about them.<br /><br />Namely, concerning the MP-ratio, a few plausible-looking question have been asked in the literature, which would have, if answered positively, made computations of MP-ratios significantly simpler. We add one more related question to these ones, and then show that, rather unexpectedly, all these questions have negative answer.<br /><br />Concerning the palindromic defect, the main result of this work is a construction of an infinite class of infinite words that have several properties that were sought after in some recent works in this area. Among the most interesting facts is that that all these words are aperiodic words of a finite positive defect, having the set of factors closed under reversal---in some recent works, the construction of even a single word having these properties turned out to be quite hard. Using these words, which we are calling <em>highly potential words</em>, we check the validity of several open&nbsp; conjectures, and for several of them we find out that they are false.</p> / <p> U tezi razmatramo aktuelne probleme u vezi s palindromskim podrečima i palindromskim faktorima konačnih i beskonačnih reči. Glavni pravac istraživanja jesu kriterijumi za određivanje koja od dve date reči je &bdquo;palindromičnija&ldquo; od druge, tj. određivanje stepena &bdquo;palindromičnosti&ldquo; date reči. Akcenat stavljamo na dva aktuelna pristupa: tzv. <em>MP-razmeru</em> i tzv. <em>palindromski defekt</em>, i odgovaramo na vi&scaron;e otvorenih pitanja u vezi s njima.<br /> <br /> Naime, u vezi sa MP-razmerom u literaturi je postavljeno vi&scaron;e pitanja, intuitivno uverljivih, koja bi, u slučaju pozitivnog razre&scaron;enja, znatno pojednostavila izračunavanje MP-razmere. Ovim pitanjima dodajemo jo&scaron; jedno srodno, a zatim pokazujemo da, prilično neočekivano, sva ova pitanja imaju negativan odgovor.<br /> <br /> U vezi s palindromskim defektom, glavni rezultat rada je konstrukcija beskonačne klase beskonačnih reči koje imaju vi&scaron;e osobina za kojima je iskazana potreba u skora&scaron;njim radovima iz ove oblasti. Među najzanimljivije spada činjenica da su sve aperiodične reči konačnog pozitivnog defekta, i da im je skup faktora zatvoren za preokretanje &ndash; u nekim skora&scaron;njim radovima konstrukcija makar jedne reči s ovim osobinama pokazala se kao prilično te&scaron;ka. Pomoću ovih reči, koje nazivamo <em>visokopotencijalne reči</em>, ispitujemo validnost vi&scaron;e otvorenih hipoteza, i za vi&scaron;e njih ustanovljavamo da nisu validne.</p>

Les besoins en puissance de calcul des processeurs sont en constante augmentation en raison de l'importance croissante des applications multimédia dans la vie courante. Ces applications requièrent de nombreux calculs avec des données de faible précision généralement issues des pixels. Le moyen le plus efficace pour exploiter le parallélisme de données de ces applications est le parallélisme dit de sous-mots (SWP pour \textit{subword parallelism}). Les opérations sont effectuées en parallèle sur des données de faible précision regroupées ce qui permet d'utiliser au mieux les ressources disponibles dimensionnées pour traiter des mots. Dans cette thèse, la conception de différents opérateurs SWP pour les applications multimédia est proposée. Une bonne adéquation entre largeur des sous-mots et largeur des données manipulées permet une meilleure utilisation des ressources et conduit ainsi à améliorer l'efficacité de l'exécution de l'application sur le processeur. Les opérateurs arithmétiques de base développés sont ensuite utilisés dans un opérateur SWP reconfigurable. Ce dernier peut être configuré pour effectuer diverses opérations multimédia avec différentes largeurs de données. L'opérateur reconfigurable peut être utilisé comme unité spécialisée ou comme co-processeur dans un processeur multimédia afin d'en améliorer les performances. La vitesse interne des différentes unités de traitement est également améliorée en représentant les nombres en système redondant plutôt qu'en système binaire. Le système redondant permet entre autre d'augmenter la vitesse des opérations arithmétiques en évitant une propagation de retenue couteuse lors d'opérations d'addition. Les résultats obtenus montrent l'intérêt en terme de performances d'utiliser des opérateurs SWP lors de l'exécution d'applications multimédia.

<p>We focus on two complexity measures of words that are invariant under the operation of reversal of a word: the palindromic defect and the MP-ratio.The palindromic defect of a given word w is dened by jwj + 1&nbsp;&nbsp; jPal(w)j, where jPal(w)j denotes the number of palindromic factors of w. We study innite words, to which this de&nbsp; nition can be naturally extended. There are many results in the literature about the so- called rich words (words&nbsp; of defect 0), while words of nite positive defect have been studied signicantly less; for some time (until recently) it was not known whether there even exist such words that additionally are aperiodic and have their set of factors closed under reversal. Among the rst examples that appeared were the so-called highly potential words. In this&nbsp; thesis we present a much more general construction,which gives a wider class of words, named generalized highly potential words, and analyze their signicance within the frames of combinatorics on words.The MP-ratio of a given n-ary&nbsp; word w is dened as the quotient jrwsj jwj ,where r and s are words such that the word rws is minimal- palindromic and that the length jrj + jsj is minimal possible; here, an n-ary word is called minimal-palindromic if it does not contain palindromic subwords of length greater than jwj n . In the binary case, it was proved that the MP-ratio is well-dened and that it is bounded from above by 4, which is the best possible upper bound. The question of well- denedness of the MP-ratio for larger alphabets was left open. In this thesis we solve that&nbsp; question in the ternary case: we show that the MP-ratio is indeed well-dened in the ternary case, that it is bounded from above by the constant 6 and that this is the best possible upper bound.</p> / <p>Izucavamo dve mere slozenosti reci koje su invarijantne u odnosu na operaciju preokretanja reci: palindromski defekt i MP-razmeru date reci.Palindromski defekt reci w denise se kao jwj + 1&nbsp;&nbsp; jPal(w)j, gde jPal(w)j predstavlja broj palindromskih faktora reci w. Mi izucavamo beskonacne reci, na koje se ova denicija moze prirodno prosiriti. Postoje mnogobrojni rezultati u vezi sa tzv. bogatim recima (reci cije je defekt 0), dok se o recima sa konacnim pozitivnim defektom relativno malo zna; tokom jednog perioda (donedavno) nije bilo poznato ni da li uopste postoje takve reci koje su,dodatno, aperiodi cne i imaju skup faktora zatvoren za preokretanje. Medu prvim primerima koji su se pojavili u literaturi su bile tzv. visokopotencijalne reci. U disertaciji cemo predstaviti znatno opstiju konstrukciju, kojom se dobija znacajno sira klasa reci, nazvanih uop stene visokopotencijalne reci, i analiziracemo njihov znacaj u okvirima kombinatorike na recima.MP-razmera date n-arne reci w denise se kao kolicnik jrwsj jwj , gde su r i s takve da je rec rws minimalno-palindromicna, i duzina jrj + jsj je najmanja moguca; ovde, za n-arnu rec kazemo da je minimalno-palindromicna ako ne sadrzi palindromsku podrec duzine vece od&nbsp; jwj n&nbsp; . U binarnom slucaju dokazano je da je MP-razmera dobro&nbsp; denisana i da je ogranicena odozgo konstantom 4, sto je i najbolja moguca granica. Dobra denisanost MP-razmere za vece alfabete je ostavljena kao otvoren problem. U ovoj tezi resavamo taj problem u ternarnom slucaju: pokazacemo da MP- razmera jeste dobro de-nisana u ternarnom slucaju, da je ogranicena odozgo sa 6, i da se ta granica ne moze poboljsati.<br />&nbsp;</p>

Avec des motivations venant du domaine de la Vérification, nous définissons une notion de WQO effectifs pour lesquels il est possible de représenter les ensembles clos et de calculer les principales opérations ensemblistes sur ces représentations. Dans une première partie, nous montrons que de nombreuses constructions naturelles sur les WQO préservent notre notion d'effectivité, prouvant ainsi que la plupart des WQOs utilisés en pratique sont effectifs. Cette partie est basée sur un article non publié dont Jean Goubault-Larrecq, Narayan Kumar, Prateek Karandikar et Philippe Schnoebelen sont co-auteurs.Dans une seconde partie, nous étudions les conséquences qu'a notre notion sur la logique du première ordre interprété sur un WQO. Bien que le fragment existentiel positif soit décidable pour tous les WQOs effectif, les perspectives de généralisation sont limitées par le résultat suivant: le fragment existentiel de la logique du première ordre sur les mots finis, ordonnés par plongement, est déjà indécidable. Ce résultat a été publié à LICS 2017 avec Philippe Schnoebelen et Georg Zetzsche. / With motivations coming from Verification, we define a notionof effective WQO for which it is possible to represent closed subsetsand to compute basic set-operations on these representations. In a firstpart, we show that many of the natural constructions that preserve WQOsalso preserve our notion of effectiveness, proving that a large class ofcommonly used WQOs are effective. This part is based on an unpublishedarticle with Jean Goubault-Larrecq, Narayan Kumar, Prateek Karandikarand Philippe Schnoebelen.In a second part, we investigate the consequences of our notion onfirst-order logics over WQOs. Although the positive existential fragmentis decidable for any effective WQO, the perspective of extension tolarger fragments is hopeless since the existential fragment is alreadyundecidable for the first-order logic over words with the subwordordering. This last result has been published in LICS 2017 with PhilippeSchnoebelen and Georg Zetzsche.

Cette thèse se situe à l'interface de trois grands domaines : la combinatoire des mots, la théorie des automates et la théorie des nombres. Plus précisément, nous montrons comment des outils provenant de la combinatoire des mots et de la théorie des automates interviennent dans l'étude de problèmes arithmétiques concernant les séries formelles à coefficients dans un corps fini.Le point de départ de cette thèse est un célèbre théorème de Christol qui caractérise les séries de Laurent algébriques sur le corps F_q(T), l'entier q désignant une puissance d'un nombre premier p, en termes d'automates finis et dont l'énoncé est : « Une série de Laurent à coefficients dans le corps fini F_q est algébrique si et seulement si la suite de ses coefficients est engendrée par un p-automate fini ». Ce résultat, qui révèle dans un certain sens la simplicité de ces séries de Laurent, a donné naissance à des travaux importants parmi lesquels de nombreuses applications et généralisations.L'objet principal de cette thèse est, dans un premier temps, d'exploiter la simplicité de séries de Laurent algébriques à coefficients dans un corps fini afin d'obtenir des résultats diophantiens, puis d'essayer d'étendre cette étude à des fonctions transcendantes arithmétiquement intéressantes. Nous nous concentrons tout d'abord sur une classe de séries de Laurent algébriques particulières qui généralisent la fameuse cubique de Baum et Sweet. Le résultat principal obtenu pour ces dernières est une description explicite de leur développement en fraction continue, généralisant ainsi certains travaux de Mills et Robbins. Rappelons que le développement en fraction continue permet généralement d'obtenir des informations très précises sur l'approximation rationnelle ; les meilleures approximations étant obtenues directement à partir de la suite des quotients partiels. Malheureusement, il est souvent très difficile d'obtenir le développement en fraction continue d'une série de Laurent algébrique, que celle-ci soit donné par une équation algébrique ou par son développement en série de Laurent. La deuxième étude que nous présentons dans cette thèse fournit une information diophantienne à priori moins précise que la description du développement en fraction continue, mais qui a le mérite de concerner toutes les séries de Laurent algébriques (à coefficients dans un corps fini). L'idée principale est d'utiliser l'automaticité de la suite des coefficients de ces séries de Laurent afin d'obtenir une borne générale pour leur exposant d'irrationalité. Malgré la généralité de ce résultat, la borne obtenue n'est pas toujours satisfaisante. Dans certains cas, elle peut s'avérer plus mauvaise que celle provenant de l'inégalité de Mahler. Cependant, dans de nombreuses situations, il est possible d'utiliser notre approche pour fournir, au mieux, la valeur exacte de l'exposant d'irrationalité, sinon des encadrements très précis de ce dernier.Dans un dernier travail nous nous plaçons dans un cadre plus général que celui des séries de Laurent algébriques, à savoir celui des séries de Laurent dont la suite des coefficients a une « basse complexité ». Nous montrons que cet ensemble englobe quelques fonctions remarquables, comme les séries algébriques et l'inverse de l'analogue du nombre \pi dans le module de Carlitz. Il possède, par ailleurs, des propriétés de stabilité intéressantes : entre autres, il s'agit d'un espace vectoriel sur le corps des fractions rationnelles à coefficients dans un corps fini (ce qui, d'un point de vue arithmétique, fournit un critère d'indépendance linéaire), il est de plus laissé invariant par diverses opérations classiques comme le produit de Hadamard / This thesis looks at the interplay of three important domains: combinatorics on words, theory of finite-state automata and number theory. More precisely, we show how tools coming from combinatorics on words and theory of finite-state automata intervene in the study of arithmetical problems concerning the Laurent series with coefficients in a finite field.The starting point of this thesis is a famous theorem of Christol which characterizes algebraic Laurent series over the field F_q(T), q being a power of the prime number p, in terms of finite-state automata and whose statement is the following : “A Laurent series with coefficients in a finite field F_q is algebraic over F_q(T) if and only if the sequence of its coefficients is p-automatic”.This result, which reveals, somehow, the simplicity of these Laurent series, has given rise to important works including numerous applications and generalizations. The theory of finite-state automata and the combinatorics on words naturally occur in number theory and, sometimes, prove themselves to be indispensable in establishing certain important results in this domain.The main purpose of this thesis is, foremost, to exploit the simplicity of the algebraic Laurent series with coefficients in a finite field in order to obtain some Diophantine results, then to try to extend this study to some interesting transcendental functions. First, we focus on a particular set of algebraic Laurent series that generalize the famous cubic introduced by Baum and Sweet. The main result we obtain concerning these Laurent series gives the explicit description of its continued fraction expansion, generalizing therefore some articles of Mills and Robbins.Unfortunately, it is often very difficult to find the continued fraction representation of a Laurent series, whether it is given by an algebraic equation or by its Laurent series expansion. The second study that we present in this thesis provides a Diophantine information which, although a priori less complete than the continued fraction expansion, has the advantage to characterize any algebraic Laurent series. The main idea is to use some the automaticity of the sequence of coefficients of these Laurent series in order to obtain a general bound for their irrationality exponent. In the last part of this thesis we focus on a more general class of Laurent series, namely the one of Laurent series of “low” complexity. We prove that this set includes some interesting functions, as for example the algebraic series or the inverse of the analogue of the real number \pi. We also show that this set satisfy some nice closure properties : in particular, it is a vector space over the field over F_q(T).

Der technologische Fortschritt gestattet die Implementierung zunehmend komplexerer Prozessorarchitekturen auf einem Schaltkreis. Ein Trend der letzten Jahre ist die Implementierung von mehr und mehr Verarbeitungseinheiten auf einem Chip. Daraus ergeben sich neue Herausforderungen für die Abbildung von Algorithmen auf solche Architekturen, denn alle Verarbeitungseinheiten sollen effizient bei der Ausführung des Algorithmus genutzt werden. Der Schwerpunkt der eingereichten Dissertation ist die Ausnutzung der Parallelität von Rechenfeldern mit Teilwortparallelität. Solche Architekturen erlauben Parallelverarbeitung auf mehreren Ebenen. Daher wurde eine Abbildungsstrategie, mit besonderem Schwerpunkt auf Teilwortparallelität entwickelt. Diese Abbildungsstrategie basiert auf den Methoden des Rechenfeldentwurfs. Rechenfelder sind regelmäßig angeordnete Prozessorelemente, die nur mit ihren Nachbarelementen kommunizieren. Die Datenein- und -ausgabe wird durch die Prozessorelemente am Rand des Rechenfeldes realisiert. Jedes Prozessorelement kann mehrere Funktionseinheiten besitzen, welche die Rechenoperationen des Algorithmus ausführen. Die Teilwortparallelität bezeichnet die Fähigkeit zur Teilung des Datenpfads der Funktionseinheit in mehrere schmale Datenpfade für die parallele Ausführung von Daten mit geringer Wortbreite. Die entwickelte Abbildungsstrategie unterteilt sich in zwei Schritte, die \"Vorverarbeitung\" und die \"Mehrstufige Modifizierte Copartitionierung\" (kurz: MMC). Die \"Vorverarbeitung\" verändert den Algorithmus in einer solchen Art, dass der veränderte Algorithmus schnell und effizient auf die Zielarchitektur abgebildet werden kann. Hierfür wurde ein Optimierungsproblem entwickelt, welches schrittweise die Parameter für die Transformation des Algorithmus bestimmt. Die \"Mehrstufige Modifizierte Copartitionierung\" wird für die schrittweise Anpassung des Algorithmus an die Zielarchitektur eingesetzt. Darüber hinaus ermöglicht die Abbildungsmethode die Ausnutzung der lokalen Register in den Prozessorelementen und die Anpassung des Algorithmus an die Speicherarchitektur, an die das Rechenfeld angebunden ist. Die erste Stufe der MMC dient der Transformation eines Algorithmus mit Einzeldatenoperationen in einen Algorithmus mit teilwortparallelen Operationen. Mit der zweiten Copartitionierungsstufe wird der Algorithmus an die lokalen Register und an das Rechenfeld angepasst. Weitere Copartitionierungsstufen können zur Anpassung des Algorithmus an die Speicherarchitektur verwendet werden. / The technological progress allows the implementation of complex processor architectures on a chip. One trend of the last years is the implemenation of more and more execution units on one chip. That implies new challenges for the mapping of algorithms on such architectures, because the execution units should be used efficiently during the execution of the algorithm. The focus of the submitted dissertation thesis is the utilization of the parallelism of processor arrays with subword parallelism. Such architectures allow parallel executions on different levels. Therefore an algorithm mapping strategy was developed, where the exploitation of the subword parallelism was in the focus. This algorithm mapping strategy is based on the methods of the processor array design. Processor arrays are regular arranged processor elements, which communicate with their neighbors elements only. The data in- and output will be realized by the processor elements on the border of the array. Each processor element can have several functional units, which execute the computational operations. Subword parallelism means the capability for splitting the data path of the functional units in several smaller chunks for the parallel execution of data with lower word width. The developed mapping strategy is subdivided in two steps, the \"Preprocessing\" and the \"Multi-Level Modified Copartitioning\" (kurz: MMC), whereat the MMC means the method of the step simultaneously. The \"Preprocessing\" alter the algorithm in such a kind, that the altered algorithm can be fast and efficient mapped on the target architecture. Therefore an optimization problem was developed, which determines gradual the parameter for the transformation of the algorithm. The \"Multi-Level Modified Copartitioning\" is used for mapping the algorithm gradual on the target architecture. Furthermore the mapping methodology allows the exploitation of the local registers in the processing elements and the adaptation of the algorithm on the memory architecture, where the processing array is connected on. The first level of the MMC is used for the transformation of an algorithm with operation based on single data to an algorithm with subword parallel operations. With the second level, the algorithm will be adapted to the local registers in the processing elements and to the processor array. Further copartition levels can be used for matching the algorithm to the memory architecture.