Automata theory, one of the main branches of theoretical computer science, established its roots in the middle of the 20th century. One of its most fundamental concepts is that of a finite automaton, a basic yet powerful model of computation. In essence, finite automata provide a method to finitely represent possibly infinite sets of strings. Such a set of strings is also called a language, and the languages which can be described by finite automata are known as regular languages. Owing to their versatility, regular languages have received a great deal of attention over the years. Other formalisms were shown to be expressively equivalent to finite automata, most notably regular grammars, regular expressions, and monadic second order (MSO) logic. To increase expressiveness, the fundamental idea underlying finite automata and regular languages was also extended to describe not only languages of strings, or words, but also of infinite words by Büchi and Muller, finite trees by Doner and Thatcher and Wright, infinite trees by Rabin, nested words by Alur and Madhusudan, and pictures by Blum and Hewitt, just to name a few examples. In a parallel line of development, Schützenberger introduced weighted automata which allow the description of quantitative properties of regular languages. In subsequent works, many of these descriptive formalisms and extensions were combined and their relationships investigated. For example, weighted regular expressions and weighted logics have been developed as well as regular expressions for trees and pictures, regular grammars for trees, pictures, and nested words, and logical characterizations for regular languages of trees, pictures, and nested words. In this work, we focus on two of these extensions and their relationship, namely weighted automata and weighted logics. Just as the classical Büchi-Elgot-Trakhtenbrot Theorem established the coincidence of regular languages with languages definable in monadic second order logic, weighted automata have been shown to be expressively equivalent to a specific fragment of a weighted monadic second order logic by Droste and Gastin. We explore several aspects of weighted automata and of this weighted logic. More precisely, the thesis considers the following topics. In the first part, we extend the classical Feferman-Vaught Theorem to the weighted setting. The Feferman-Vaught Theorem is one of the fundamental theorems in model theory. The theorem describes how the computation of the truth value of a first order sentence in a generalized product of relational structures can be reduced to the computation of truth values of first order sentences in the contributing structures and the evaluation of an MSO sentence in the index structure. The theorem itself has a long-standing history. It builds upon work of Mostowski, and was shown in subsequent works to hold true for MSO logic. Here, we show that under appropriate assumptions, the Feferman-Vaught Theorem also holds true for a weighted MSO logic with arbitrary commutative semirings as weight structure. In the second part, we lift four decidability results from max-plus word automata to max-plus tree automata. Max-plus word and tree automata are weighted automata over the max-plus semiring and assign real numbers to words or trees, respectively. We show that, like for max-plus word automata, the equivalence, unambiguity, and sequentiality problems are decidable for finitely ambiguous max-plus tree automata, and that the finite sequentiality problem is decidable for unambiguous max-plus tree automata. In the last part, we develop a logic which is expressively equivalent to quantitative monitor automata. Introduced very recently by Chatterjee, Henzinger, and Otop, quantitative monitor automata are an automaton model operating on infinite words. Quantitative monitor automata possess several interesting features. They are expressively equivalent to a subclass of nested weighted automata, an automaton model which for many valuation functions has decidable emptiness and universality problems. Also, quantitative monitor automata are more expressive than weighted Büchi-automata and their extension with valuation functions. We introduce a new logic which we call monitor logic and show that it is expressively equivalent to quantitative monitor automata.

No description available.

In dieser Arbeit wird das Fraïssé-Hrushowskis Amalgamationsverfahren in Zusammenhang mit nilpotenten graduierten Lie Algebren über einem endlichen Körper untersucht. Die Prädimensionen die in der Konstruktion auftauchen sind mit dem gruppentheoretischen Begriff der Defizienz zu vergleichen, welche auf homologische Methoden zurückgeführt werden kann. Darüber hinaus wird die Magnus-Lazardsche Korrespondenz zwischen den oben genannten Lie Algebren und nilpotenten Gruppen von Primzahl-Exponenten beschrieben. Dabei werden solche Gruppen durch die Baker-Haussdorfsche Formel in den entsprechenden Algebren definierbar interpretiert. Es wird eine omega-stabile Lie Algebra von Nilpotenzklasse 2 und Morleyrang omega + omega erhalten, indem man eine unkollabierte Version der von Baudisch konstruierten "new uncountably categorical group" betrachtet. Diese wird genau analysiert. Unter anderem wird die Unabhängigkeitsrelation des Nicht-Gabelns durch die Konfiguration des freien Amalgams charakterisiert. Mittels eines induktiven Ansatzes werden die Grundlagen entwickelt, um neue Prädimensionen für Lie Algebren der Nilpotenzklassen größer als zwei zu schaffen. Dies erweist sich als wesentlich schwieriger als im Fall 2. Wir konzentrieren uns daher auf die Nilpotenzklasse 3, als Induktionsbasis des oben genannten Prozesses. In diesem Fall wird die Invariante der Defizienz auf endlich erzeugte Lie Algebren adaptiert. Erstes Hauptergebnis der Arbeit ist der Nachweis dass diese Definition zu einem vernüftigen Begriff selbst-genügender Erweiterungen von Lie Algebren führt und sehr nah einer gewünschten Prädimension im Hrushovskischen Sinn ist. Wir zeigen – als zweites Hauptergebnis – ein erstes Amalgamationslemma bezüglich selbst-genügender Einbettungen. / In this work, the so called Fraïssé-Hrushowski amalgamation is applied to nilpotent graded Lie algebras over the p-elements field with p a prime. We are mainly concerned with the uncollapsed version of the original process. The predimension used in the construction is compared with the group theoretical notion of deficiency, arising from group Homology. We also describe in detail the Magnus-Lazard correspondence, to switch between the aforementioned Lie algebras and nilpotent groups of prime exponent. In this context, the Baker-Hausdorff formula allows such groups to be definably interpreted in the corresponding algebras. Starting from the structures which led to Baudisch’ new uncountably categorical group, we obtain an omega-stable Lie algebra of nilpotency class 2, as the countable rich Fraïssé limit of a suitable class of finite Lie algebras. We study the theory of this structure in detail: we show its Morley rank is omega+omega and a complete description of non-forking independence is given, in terms of free amalgams. In a second part, we develop a new framework for the construction of deficiency-predimensions among graded Lie algebras of nilpotency class higher than 2. This turns out to be considerably harder than the previous case. The nil-3 case in particular has been extensively treated, as the starting point of an inductive procedure. In this nilpotency class, our main results concern a suitable deficiency function, which behaves for many aspects like a Hrushovski predimension. A related notion of self-sufficient extension is given. We also prove a first amalgamation lemma with respect to self-sufficient embeddings.

Die vorliegende Dissertation besteht aus zwei Teilen, deren gemeinsames Thema in der Frage besteht, wie mächtig Zufall als Berechnungsressource ist. Im ersten Teil beschäftigen wir uns mit zufälligen Strukturen, die -- mit hoher Wahrscheinlichkeit -- Eigenschaften haben können, die von Computeralgorithmen genutzt werden können. In zwei konkreten Fällen geben wir bis dahin unbekannte deterministische Konstruktionen solcher Strukturen: Wir derandomisieren eine randomisierte Reduktion von Alekhnovich und Razborov, indem wir bestimmte unbalancierte bipartite Expandergraphen konstruieren, und wir geben eine Reduktion von einem Problem über bipartite Graphen auf das Problem, den minmax-Wert in Dreipersonenspielen zu berechnen. Im zweiten Teil untersuchen wir die Ausdrucksstärke verschiedener Logiken, wenn sie durch zufällige Relationssymbole angereichert werden. Unser Ziel ist es, Techniken aus der deskriptiven Komplexitätstheorie für die Untersuchung randomisierter Komplexitätsklassen nutzbar zu machen, und tatsächlich können wir zeigen, dass unsere randomisierten Logiken randomisierte Komlexitätsklassen einfangen, die in der Komplexitätstheorie untersucht werden. Unter Benutzung starker Ergebnisse über die Logik erster Stufe und die Berechnungsstärke von Schaltkreisen beschränkter Tiefe geben wir sowohl positive als auch negative Derandomisierungsergebnisse für unsere Logiken. Auf der negativen Seite zeigen wir, dass randomisierte erststufige Logik gegenüber normaler erststufiger Logik an Ausdrucksstärke gewinnt, sogar auf Strukturen mit einer eingebauten Additionsrelation. Außerdem ist sie nicht auf geordneten Strukturen in monadischer zweitstufiger Logik enthalten, und auch nicht in infinitärer Zähllogik auf beliebigen Strukturen. Auf der positiven Seite zeigen wir, dass randomisierte erststufige Logik auf Strukturen mit einem unären Vokabular derandomisiert werden kann und auf additiven Strukturen in monadischer Logik zweiter Stufe enthalten ist. / This thesis is comprised of two main parts whose common theme is the question of how powerful randomness as a computational resource is. In the first part we deal with random structures which possess -- with high probability -- properties than can be exploited by computer algorithms. We then give two new deterministic constructions for such structures: We derandomise a randomised reduction due to Alekhnovich and Razborov by constructing certain unbalanced bipartite expander graphs, and we give a reduction from a problem concerning bipartite graphs to the problem of computing the minmax-value in three-player games. In the second part we study the expressive power of various logics when they are enriched by random relation symbols. Our goal is to bridge techniques from descriptive complexity with the study of randomised complexity classes, and indeed we show that our randomised logics do capture complexity classes under study in complexity theory. Using strong results on the expressive power of first-order logic and the computational power of bounded-depth circuits, we give both positive and negative derandomisation results for our logics. On the negative side, we show that randomised first-order logic gains expressive power over standard first-order logic even on structures with a built-in addition relation. Furthermore, it is not contained in monadic second-order logic on ordered structures, nor in infinitary counting logic on arbitrary structures. On the positive side, we show that randomised first-order logic can be derandomised on structures with a unary vocabulary and is contained in monadic second-order logic on additive structures.

This thesis examines the effects of Culture, the Unified Theory of Acceptance and Use of Technology (UTAUT), Expectation Confirmation Theory (ECT) and Technology Readiness (TR) on the satisfaction and usage continuance intention of Internet banking customers within the Saudi Arabian context. The aim is to develop and test a new framework for use in determining the factors that affect Internet banking customers’ actual usage behaviours, with a special focus on the role of cognitive processes, and cultural and personal psychological traits. This research uses cross-sectional survey questionnaire methods within a quantitative approach. 261 valid responses were received. Structural Equation Modelling (SEM) was used to test the hypothesised relationships within the research model in Analysis of Moment Structures (AMOS 20) software. ECT is well established in conventional marketing literature and explains how cognitive beliefs and affects lead to customers’ repurchasing behaviour. It was first adopted for the Information Systems (IS) context and then customised to explain IS continuance intention behaviour. However, previous ECT customisations in the IS context present a significant knowledge gap because technology-based services are sensitive to individuals’ psychological traits, which ECT does not account for. This research integrates psychological traits and culture into the ECT framework to explain customer satisfaction and continuance intentions in the context of Internet banking usage. It combines ECT with the UTAUT in order to expand ECT to include more cognitive beliefs. Then it integrates TR and Culture to account for psychological and sociological traits. The results present a new contribution to the body of knowledge by validating a theoretically backed integration of the above models into one structural model. This model broadens the understanding of the factors that influence IS satisfaction and usage continuance intention. Compared to previous studies, the explanatory power of this model is a major improvement, with an R2 of (0.61) for usage continuance intention.

Customers adoption of Internet banking has become a widely-researched topic, although it is fair to state that some research gaps still exist. This research aims to fill some of the research gaps by examining the factors that determine the relevant behaviour of three different categories of Internet banking customers in China (i.e. current users, non-users, and discontinued users), and by developing two conceptual models that are derived from different, but complementary, theoretical approaches. The Decision Making Model and the Service and Relationship Evaluation Model are developed in this research. The Decision Making Model is grounded in the technology acceptance model (TAM) and it incorporates an additional construct of perceived value of using Internet banking. Additionally, the Service and Relationship Evaluation Model is derived from the service quality evaluation and relationship quality evaluation literature. Unlike in most other Internet banking adoption studies, these two conceptual models are used complementarily to deliver a comprehensive understanding of customers Internet banking adoption in China. The models are tested using a sample of 614 Chinese Internet banking customers collected via mall-intercept personal interviews based on questionnaires. Partial Least Square (PLS) path modelling and mediation analysis are applied to test the hypotheses advanced in the two models. The key findings of this research show that perceived value is a major factor for explaining customers Internet banking adoption, thus indicating to the banks that they should reduce costs associated with using Internet banking while providing more (perceived) benefits to customers; the importance of incorporating perceived value in Internet banking adoption model(s) is also demonstrated. The findings also confirm that perceived usefulness and perceived ease of use are important factors that determine the adoption of Internet banking by all categories of customers. Current users and non-users perceptions of their behavioural control over using Internet banking contribute to their adoption of Internet banking, and such control perceptions are shaped by self-efficacy, perceived government support and technological support. Additionally, it is demonstrated that both current users and discontinued users perceived value and perceived service quality of Internet banking have positive associations with their satisfaction with Internet banking, which lead to their Internet banking adoption. Moreover, the findings reveal that current users are more likely to continue with Internet banking if they are affectively committed to their banks; they are less likely to continue with Internet banking if they are calculatively committed to their banks due to the costs associated with leaving the banks. These therefore indicate the importance of establishing high-quality customer-bank relationships and placing less strict switching cost barriers that impose less pressure on their existing customers. This research contributes to the Internet banking adoption literature by (i) identifying the important category of Internet banking discontinued users, apart from current users and non-users; and (ii) using two complementary conceptual models, which are grounded in different theoretical streams, to investigate the relevant adoption behaviour of all three categories of Internet banking customers. It hence delivers a comprehensive understanding of personal customers adoption of Internet banking in China.

No description available.

Les structures menues apparaissent dans les années 60 en lien avec la conjecture de Vaught. Les structures minces englobent à la fois les structures minimales et menues. Les ensembles définissables d'une structure mince sont rangés par le rang de Cantor-Bendixson. Nous présentons des propriétés de calcul de ce rang, une condition de chaîne descendante locale sur les groupes acl(0)-définissables ainsi qu'une notion de presque stabilisateur local, et en déduisons des propriétés algébriques des structures minces : un corps mince de caractéristique positive est localement de dimension finie sur son centre, et un groupe mince infini a un sous groupe abélien infini. Nous nous intéressons ensuite aux structures menues infiniment définissables, et montrons que les groupes d'arité finie infiniment 0-définissable sont l'intersection de groupes définissables. Nous étendons le résultat aux demi-groupes, anneaux, corps, catégories et groupoïdes infiniment 0-définissables, et donnons des résultats de définissabilité locale pour les groupes et corps simples et menus, infiniment définissables sur des paramètres quelconques. Enfin, nous réintroduisons le rang de Cantor dans son contexte topologique et montrons que la dérivée de Cantor peut être vue comme un opérateur de dérivation dans un semi-anneau d'espaces topologiques. Dans l'idée de trouver un rang de Cantor global pour les théories stables, nous essayons de nous débarrasser du mot dénombrable omniprésent lorsque l'on fait de la topologie, en le remplaçant par un cardinal régulier k. Nous développons une notion d'espace k-métrique, de k-topologie, de k-compacité etc. et montrons un k-analogue du lemme de métrisabilité d'Urysohn, et du théorème de Cantor-Bendixson. / Abstract. Small structures appear in the '60s together with Vaught's conjecture. Weakly small structures include both minimal and small structures. Definable sets in a weakly small structure are ranked by Cantor-Bendixson rank. We show computational properties of this rank, which imply a local descending chain condition on acl(0)-definable subgroups, and introduce a notion of local almost stabiliser. We deduce algebraic properties of weakly small structures. Among them, a weakly small field of positive characteristic is locally finite dimensional over its centre, and an infinite weakly small group has an infinite abelian subgroup. We then turn to small type-definable structures, showing that finitary small type 0-de_nable groups are the intersection of definable groups. We extend the result to finitary small type 0- definable monoids, rings, fields, categories and groupoids. We give local definability results concerning groups and fields type definable over an arbitrary set of parameters in small and simple theories. Finally, we reintroduce the Cantor Bendixson rank in its topological context, and show that the Cantor derivative can be seen as a derivation in a semi-ring of topological spaces. In an attempt to find a global Cantor rank for stable structures, we try to eliminate the word denumerable, omnipresent when one does topology, by replacing it by a regular cardinal k. We develop the notions of k-metrisable space, k-topology, k-compactness etc. and show an analogue of Urysohn's metrisability lemma and Cantor-Bendixson theorem.

La notion de T-radical d’un idéal permet à G.Cherlin de démontrer un Nullstellensatz dans les théories inductives d’anneaux. Nous proposons une analyse modèle-théorique de phénomènes connexes. En premier lieu, une réciproque de ce théorème nous conduit à une caractérisation des corps algébriquement clos, suggérant une version “positive” du travail de Cherlin, la théorie des idéaux T-radiciels. Ceux-ci se caractérisent par un théorème de représentation et sont associés à un théorème des zéros “positif”. Ces résultats se généralisent à la logique du premier ordre : grâce à la notion de classe spéciale, nous développons ensuite une théorie logique des idéaux. On peut encore parler d’idéaux premiers et radiciels, relativement à une classe de structures. Dans ce cadre, le théorème de représentation est une propriété intrinsèque des classes spéciales et le théorème des zéros une propriété de préservation logique, que nous appelons “complétude géométrique” et qui entretient des rapports étroits avec la modèle-complétude positive. Les algèbres basées en groupes de P.Higgins permettent d’appliquer ces résultats aux théories modèle-complètes de corps avec opérateurs additionnels. Dans certains cas “noethériens”, l’algèbre de coordonnées est un invariant algébrique des “variétés affines”. Enfin, il est possible à partir d’un ensemble de formules E de généraliser les classes spéciales et autres classes de structures. Notre théorie des idéaux logiques est de plus un cas particulier du phénomène de localisation étudié par M.Coste ; dans certaines situations, un bon choix de formules permet d’identifier les types complets d’une “algèbre” à des types de localisation / The notion of T-radical of an ideal allows G.Cherlin to prove a Nullstellensatz for inductive ring theories.We present here a model-theoretic analysis of closely related phenomena. At first, a reverse of this theorem leeds us to a characterization of algebraically closed fields, suggesting a “positive” version of Cherlin’s work, the theory of T-radical ideals. These are characterized by a representation theorem and associated to a “positive” Nullstellensatz. Those results are generalized to first order logic : thanks to the notion of special class, we then develop a logical theory of ideals. One may still speak about prime and radical ideals, relatively to a class of structures. In this setting, the representation theorem is an intrinsic property of special classes and the Nullstellensatz a logical preservation property, which we call “geometric completeness” and which is closely linked to positive model-completeness. The group-based algebras of P.Higgins allow us to apply these results to model-complete theories of fields with additional operators. In certain “noetherian” cases, the coordinate algebra is an algebraic invariant of “affine algebraic sets”. At last, it is possible from a set of formulas E to generalize special and other classes of structures. Moreover, our theory of logical ideals is a particular case of the localisation phenomenon studied by M.Coste ; in certain situations, a good choice of formulasleeds to an identification of the complete types of a given “algebra” with some localisation types

Este trabalho tem como foco principal estabelecer condições gerais suficientes para que uma expansão do corpo ordenado dos reais por funções com domínio em Rn seja modelo completa e o-minimal. Para tanto, faremos uma abordagem sob o ponto de vista de estruturas fracas o-minimais, conforme o trabalho de Charbonnel e Wilkie. Além disso, ao analisar condições adicionais, podemos obter a seguinte generalização de um trabalho de Gabrielov: uma expansão o-minimal do corpo ordenado dos reais por funções C infinito restritas, que é polinomialmente limitada e fechada sob diferenciação parcial, é modelo completa. / The main focus of this dissertation lies in establishing some general sufficient conditions for an expansion of the real ordered field by functions with domains Rn to be model complete and o-minimal. We approach this subject from the point of view of the o-minimal weak structures, by following the work of Charbonnel and Wilkie. Furthermore, when considering additional conditions, we are able to obtain the following generalization of a Gabrielovs result: an expansion of the real ordered field by restricted smooth functions, which is polynomially bounded and closed under partial differentiation, is model complete.