none

<p>New emission legislations introduced in the European Union and the U.S. have made truck manufacturers face stricter requirements for low emissions and on-board diagnostic systems. The on-board diagnostic system typically consists of several tests that are run when the truck is driving. One way to construct such tests is to use so called consistency relations. A consistency relation is a relation with known variables that in the fault free case always holds. Calculation of a consistency relation typically involves eliminating unknown variables from a set of equations.</p><p>To eliminate variables from a differential polynomial system, methods from differential algebra can be used. In this thesis, the purely algebraic Gröbner basis algorithm and the differential Rosenfeld-Gröbner algorithm implemented in the Maple package Diffalg have been compared and evaluated. The conclusion drawn is that there are no significant differences between the methods. However, since using Gröbner basis requires differentiations to be made in advance, the recommendation is to use the Rosenfeld-Gröbner algorithm.</p><p>Further, attempts to calculate consistency relations using the Rosenfeld-Gröbner algorithm have been made to a real application, a model of a Scania diesel engine. These attempts did not yield any successful results. It was only possible to calculate one consistency relation. This can be explained by the high complexity of the model.</p>

New emission legislations introduced in the European Union and the U.S. have made truck manufacturers face stricter requirements for low emissions and on-board diagnostic systems. The on-board diagnostic system typically consists of several tests that are run when the truck is driving. One way to construct such tests is to use so called consistency relations. A consistency relation is a relation with known variables that in the fault free case always holds. Calculation of a consistency relation typically involves eliminating unknown variables from a set of equations. To eliminate variables from a differential polynomial system, methods from differential algebra can be used. In this thesis, the purely algebraic Gröbner basis algorithm and the differential Rosenfeld-Gröbner algorithm implemented in the Maple package Diffalg have been compared and evaluated. The conclusion drawn is that there are no significant differences between the methods. However, since using Gröbner basis requires differentiations to be made in advance, the recommendation is to use the Rosenfeld-Gröbner algorithm. Further, attempts to calculate consistency relations using the Rosenfeld-Gröbner algorithm have been made to a real application, a model of a Scania diesel engine. These attempts did not yield any successful results. It was only possible to calculate one consistency relation. This can be explained by the high complexity of the model.

Normal-hearing listeners can locate sound sources, using binaural cues for azimuth angle. These binaural differences in the timing and intensity of sound arriving at the two ears, interaural time differences (ITDs) and interaural intensity differences (IIDs), also support selective listening in multi-talker environments. Auditory-brainstem neurons of the medial superior olive (MSO) and lateral superior olive (LSO) encode ITD in the envelope of sound (ITDENV) and in the temporal fine structure of low-frequency sound (ITDTFS); LSO neurons encode IID. Bilateral-cochlear-implant (bCI) listeners generally receive only IID and ITDENV. Experimental bCI pulse-bursts overcome adaptation, and convey electrical ITDTFS. Improving the understanding of mechanisms for ITD sensitivity can help bCI developers convey acoustic ITDTFS. In this dissertation, models for auditory-brainstem neurons are developed that explain human ability to detect small differences in ITD, as neuronal and MSO population mechanisms. Promoting binaural-coincidence detection and limiting backpropagation, model MSO ion-channels set resting potentials that reproduce dendritic and somatic KLT activation, somatic Na+ inactivation, and a lower amount of axonal Na+ inactivation. Sensitivity to ITDTFS in moderately fast and very fast model MSO neurons collectively match physiological data from 150 to 2000 Hz. The best-ITD (the ITD of highest spike rate) can be made contralateral-leading, by contralateral inhibition of moderate speed, or by asymmetric axon location, leveraging dendritic filtering. Leveraging standard binaural-display models, neuronal populations based on these model MSO neurons match normal-hearing human discrimination thresholds for ITDTFS in sine tones from 39 to 1500 Hz. Adaptation before binaural interaction helps model MSO neurons glimpse the ITDTFS of sound direct from a source, before reflected sound arrives from different directions. With inputs from adapting model spherical bushy cells, a moderately fast model MSO neuron reproduces in vivo responses to amplitude-modulated binaural beats, with a frequency-dependent emphasis of rising vs. peak sound-pressure for ITDTFS encoding, which reflects human ITD detection and reverberation times in outdoor environments. Distinct populations of model LSO neurons, spanning the range of electrical membrane impedance as a function of frequency in LSO neurons, collectively reflect discrimination thresholds for ITDENV in transposed tones across carrier frequency (4-10 kHz) and modulation rate (32-800 Hz). / 2022-09-28T00:00:00Z

Cette thèse étudie les structures dont la théorie au second ordremonadique est décidable, et en particulier la hiérarchie à pile. Onpeut définir celle-ci comme la hiérarchie pour $n$ des graphesd'automates à piles imbriquées $n$ fois ; une définition externe, partransformations de graphes, est également disponible. Nous nousintéressons à l'exemple des ordinaux. Nous montrons que les ordinauxplus petits que $epsilon_0$ sont dans la hiérarchie, ainsi que des graphesporteurs de plus d'information, que l'on appelle "graphecouvrants''. Nous montrons ensuite l'inverse : tous les ordinaux de lahiérarchie sont plus petits que $epsilon_0$. Ce résultat utilise le fait queles ordres d'un niveau sont en fait isomorphes aux structures desfeuilles des arbres déterministes dans l'ordre lexicographique, aumême niveau. Plus généralement, nous obtenons une caractérisation desordres linéaires dispersés dans la hiérarchie. Dans un troisièmetemps, nous resserons l'intérêt aux ordres de type $omega$ --- les mots infinis --- pour montrer que les mots du niveau 2 sont les motsmorphiques, ce qui nous amène à une nouvelle extension au niveau 3 / This thesis studies the structures with decidable monadic second-ordertheory, and in particular the pushdown hierarchy. The latter can bedefined as the family for $n$ of pushdown graphs with $n$ timesimbricated stacks ; another definition is by graph transformations. Westudy the example of ordinals. We show that ordinals smaller that $epsilon_0$are in the hierarchy, along with graphs called "covering graphs'', which carry more data than ordinals. We show then the converse : allordinals of the hierarchy are smaller than $epsilon_0$. This result uses thefact that linear orders of a level are actually isomorphic to thestructure of leaves of deterministic trees by lexicographic ordering, at the same level. More generally, we obtain a characterisation ofscattered linear orders in the hierarchy. We finally focus on the caseof orders of type $omega$ --- infinite words --- and show that morphicwords are exactly words of the second level of the hierarchy. Thisleads us to a new definition of words for level 3

Cette thèse a eu pour objectif d'étudier des questions naturelles de définissabilité autour des transducteurs bidirectionnels.Il est bien connu que les transducteurs bidirectionnels définissent une plus grande classe de transductions que celles des transducteurs unidirectionnels. La première question que nous avons étudiée est donc de décider si un transducteur bidirectionnel est définissable par un transducteur unidirectionnel. Il a été montré en 2013 que cette question est décidable pour des transducteurs fonctionnels (nous montrons aussi en paralèlle que cette question devient indécidable si les transducteurs ne sont plus fonctionnels) mais la complexité de la procédure de décision était non-élémentaire.Nous proposons une caractérisation de la "définissabilité par transducteur unidirectionnel" décidable en espace doublement exponentiel. Cette caractérisation est effective en ce sens qu'elle produit en temps triplement exponentiel le transducteur équivalent. De plus, nous avons étudié ce problème aussi pour les transducteurs "sweeping", pour lesquels la procédure de décision et la construction du transducteur équivalent requièrent une exponentielle de moins. Comme nous avons par ailleurs montré qu'il existe des familles de fonctions réalisables de façon unidirectionnelle avec au minimum deux sauts exponentiels, notre procédure est optimale dans le cas "sweeping".Le fait d'avoir particulièrement étudié les transducteurs"sweeping" nous a poussé à étudier d'autres questions dedéfinissabilité~: est-ce qu'un transducteur donné estréalisable par un transducteur sweeping ? Et par un transducteursweeping réalisant au maximum k passages ? Nous montrons que cesquestions sont décidables avec les mêmes complexitésobtenues précédemment. Comme nous avons montré qu'ilexiste une borne sur le nombre de passages nécéssaires pourréaliser avec un transducteur sweeping une transductiondonnée, cela nous permet aussi de minimiser le nombre de passages d'untransducteur sweeping.Enfin nous avons cherché à caractériser la classe destransductions sweeping dans d'autres modèles de transductions,les Streaming String Transducers (SST) et lestransductions MSO. Cela a en autres permis, en établissant unecorrespondance entre le nombre de passages des transducteurssweeping et le nombre de registres d'une sous-classe de SST, deminimiser le nombre de registres pour une classe intéressantede SST. Dans l'ensemble, notre travail a permis de couvrir l'ensembledes relations entre ces modèles, et les questions dedéfinissabilité qui se posent naturellement. / The goal of this thesis was to study definability questionsabout finite-state transducers and in particular two-waytransducers. It is known that two-way transducers cover a larger classof transductions than one-way transducers. Then the first question wetackled is the one-way definability problem: is it possible torealize a given two-way transduction by a one-way transducer? Thisproblem was shown to be decidable for functionaltransducers (we also show as a side result that one-way definability becomes undecidable for non-functional transducers) but the decision procedure had non-elementary complexity.We proposed a characterization of one-way definability thatallows us to decide it in double-exponential space, and provide anequivalent one-way transducer of triple-exponential size. We firststudied this question for a restricted class, namely sweepingtransducers, for which the decision procedure and the construction ofthe one-way transducer take one less exponential. For suchtransducers, our procedure is optimal in the sense that we have shownthat there exists a family of functions that are one-way definable andfor which an equivalent one-way transducer requires doubly exponentialsize.The study of sweeping transducers raised other definability questions: Is a given transducer equivalent to some sweeping transducer? And to some sweeping transducer that performs at most k passes? We showed that those questions are decidable and the decision procedure, as well as the equivalent transducer, have the same complexity as in the one-way case. Moreover, as we have shown that there exists a bound on the number of passes required to realize a transduction by a sweeping transducer, we managed to obtain a procedure to minimize the number of passes of a sweeping transducer.Finally we tried to characterize sweeping transducers in other models for regular transductions such as Streaming String transducers (SST) and MSO transductions. As we obtained an equivalence between the number of passes of a sweeping transducer and the number of registers of the equivalent SST we provided a minimization procedure for the number of registers of a large class of SST's. To conclude, our work allowed us to provide a good overall understanding of the definability questions between the models for regular transductions and in particular regarding the resources, whether it is the number of passes (and of course one-way definability is crucial in that aspect) or the number of registers.

In the present thesis we provide compact extended formulations for a wide range of polytopes associated with the constraint satisfaction problem (CSP), monadic second order logic (MSO) on graphs, and extensions of MSO, when the given instances have bounded treewidth. We show that our extended formulations have additional useful properties, and we uncover connections between MSO and CSP. We conclude that a combination of the MSO logic, CSP and geometry provides an extensible framework for the design of compact extended formulations and parameterized algorithms for graphs of bounded treewidth. Putting our framework to use, we settle the parameterized complexity landscape for various extensions of MSO when parameterized by two important graph width parameters, namely treewidth and neighborhood diversity. We discover that the (non)linearity of the MSO extension determines the difference between fixedparameter tractability and intractability when parameterized by neighborhood diversity. Finally, we study shifted combinatorial optimization, a new nonlinear optimization framework generalizing standard combinatorial optimization, and provide initial findings from the perspective of parameterized complexity

Cette thèse étudie les structures dont la théorie au second ordremonadique est décidable, et en particulier la hiérarchie à pile. Onpeut définir celle-ci comme la hiérarchie pour $n$ des graphesd'automates à piles imbriquées $n$ fois ; une définition externe, partransformations de graphes, est également disponible. Nous nousintéressons à l'exemple des ordinaux. Nous montrons que les ordinauxplus petits que $epsilon_0$ sont dans la hiérarchie, ainsi que des graphesporteurs de plus d'information, que l'on appelle "graphecouvrants''. Nous montrons ensuite l'inverse : tous les ordinaux de lahiérarchie sont plus petits que $epsilon_0$. Ce résultat utilise le fait queles ordres d'un niveau sont en fait isomorphes aux structures desfeuilles des arbres déterministes dans l'ordre lexicographique, aumême niveau. Plus généralement, nous obtenons une caractérisation desordres linéaires dispersés dans la hiérarchie. Dans un troisièmetemps, nous resserons l'intérêt aux ordres de type $omega$ --- les mots infinis --- pour montrer que les mots du niveau 2 sont les motsmorphiques, ce qui nous amène à une nouvelle extension au niveau 3

Endliche Wortautomaten ermöglichen es, reguläre Wortsprachen sowohl zu erkennen als auch zu erzeugen. Julius Richard Büchi gelang es, diese erkennbaren Wortsprachen mithilfe der monadischen Logik zweiter Stufe, kurz MSO, zu charakterisieren [7, 19]. Dieses Ergebnis wurde dann auf erkennbare Baumsprachen, das heißt Mengen von geordneten Bäumen, die durch einenAufwärtsbaumautomaten erkannt werden, erweitert [11, 28]. Anstelle der <-Relation auf den Positionen eines Wortes tritt dabei die Kindrelation edgei(x; y) für die Positionen eines Baumes. Die erkennbaren Wort- und Baumsprachen haben breite Anwendung in der Informatik gefunden. Zu den bekanntesten gehören beispielsweise reguläre Ausdrücke und Syntaxbäume vieler Programmiersprachen. Im Zusammenspiel mit XML ist die Schemasprache RelaxNG zur Dokumentvalidierung [9, 29], im Gegensatz zu XML-Schema, durch die reiche Theorie erkennbarer Baumsprachen fundiert.

Quantitative aspects of systems, like the maximal consumption of resources, can be modeled by weighted automata. The usual approach is to weight transitions with elements of a semiring and to define the behavior of the weighted automaton by mul- tiplying the transition weights along a run. In this thesis, we define and investigate a new class of weighted automata over unranked trees which are defined over valuation monoids. By turning to valuation monoids we use a more general cost model: the weight of a run is now determined by a global valuation function. Besides the binary cost functions implementable via semirings, valuation functions enable us to cope with average and discounting. We first investigate the supports of weighted unranked tree automata over valuation monoids, i.e., the languages of all words which are evalu- ated to a non-zero value. We will furthermore consider the support of several other weighted automata models over different structures, like words and ranked trees. Next we prove a Nivat-like theorem for the new weighted unranked tree automata. More- over, we give a logical characterization for them. We show that weighted unranked tree automata are expressively equivalent to a weighted MSO logic for unranked trees. This solves an open problem posed by Droste and Vogler. Finally, we present a Kleene- type result for weighted ranked tree automata over valuation monoids.