There exists an interesting relationships between two seemingly distinct fields: logic from the field of Model Theory, which deals with the truth of statements about discrete structures; and Computational Complexity, which deals with the classification of problems by how much of a particular computer resource is required in order to compute a solution. This relationship is known as Descriptive Complexity and it is the primary application of the tools from Model Theory when they are restricted to the finite; this restriction is commonly called Finite Model Theory. In this thesis, we investigate the extension of the results of Descriptive Complexity from classes of decision problems to classes of optimisation problems. When dealing with decision problems the natural mapping from true and false in logic to yes and no instances of a problem is used but when dealing with optimisation problems, other features of a logic need to be used. We investigate what these features are and provide results in the form of logical frameworks that can be used for describing optimisation problems in particular classes, building on the existing research into this area. Another application of Finite Model Theory that this thesis investigates is the relative expressiveness of various fragments of an extension of modal logic called hybrid modal logic. This is achieved through taking the Ehrenfeucht-Fraïssé game from Model Theory and modifying it so that it can be applied to hybrid modal logic. Then, by developing winning strategies for the players in the game, results are obtained that show strict hierarchies of expressiveness for fragments of hybrid modal logic that are generated by varying the quantifier depth and the number of proposition and nominal symbols available.

No description available.

Designers of effective and efficient fuzzy systems have long recognised the value of inferential hybridity in the implementation of sparse fuzzy rule based systems. Which is to say: such systems should have recourse to fuzzy rule interpolation (FRI) only when no rule matches a given observation; otherwise, when an observation partially or exactly matches at least one of the rules of the sparse rule base, a compositional rule of inference (CRI) should be used in order to avoid the computational overheads of interpolation. Sparse fuzzy rule bases are constructed by experts or derived from data and may support FRI reasoning in long run. However, two potential problems arise: (1) a system's requirements may change over time leading to rule redundancy; and (2) the system may cease in the long run to provide precise and pertinent results. The need to maintain the concurrency and accuracy of a sparse fuzzy rule base, in order that it generates the most precise and relevant results possible, motivates consideration of a dynamic (real-time) fuzzy rule base. This thesis therefore presents a framework of dynamic fuzzy rule interpolation (D-FRI), integrated with general fuzzy inference (CRI), which uses the FRI result set itself for the selection, combination and promotion of informative, frequentlyused intermediate rules into the existing rule base. Here two versions of the D-FRI approach are presented:k-means-based and GA-aided. Integration uses the concept of -cut overlapping between fuzzy sets to decide an exact or partial matching between rules and observation so that CRI can be utilised for reasoning. Otherwise, the best closest rules are selected for FRI by exploiting the centre of gravity (COG), Hausdorff distance (HD) and earth mover's distance (EMD) metrics. Testing seeks to show that dynamically-promoted rules generate results of greater accuracy and robustness than would be achievable through conventional FRI tout court, and to support the claim that the D-FRI approach results in a more effective interpolative reasoning system. To this end, an implementation of D-FRI is applied to the problem domain of intrusion detection systems (IDS), by integrating it with Snort in order to improve port-scanning detection and increase the level of accuracy of alert predictions.

Fuzzy inference is an effective means for representing and handling vagueness and imprecision. As a particular type of fuzzy inference, fuzzy rule interpolation enhances the performance of the inference when a given observation has no overlap with the antecedent values of any of the existing rules. In such cases, conventional fuzzy inference methods cannot derive a conclusion, but fuzzy rule interpolation methods can still obtain a certain conclusion. Unfortunately, very little of the existing work on fuzzy rule interpolation can conjunctively handle more than one form of uncertainty in the rules or observations. In particular, the difficulty in defining the required precise-valued membership functions for the fuzzy sets that are used by conventional fuzzy rule interpolation techniques significantly restricts their application. In this thesis, a novel framework termed 'higher order fuzzy rule interpolation' is proposed in an attempt to address such difficulties. The proposed framework allows the representation, handling and utilisation of different types of uncertainty in knowledge. This allows transformation-based fuzzy rule interpolation techniques to harness and utilise the additional uncertainty in order to implement a fuzzy interpolative reasoning system. Final conclusions can then be derived by performing higher order interpolation over this representation. The techniques for the representation and handling of uncertainty are organised in this framework such that in circumstances when different types of uncertainty are encountered the inference process can deal with them in an appropriate way. A roughfuzzy set based rule interpolation approach is proposed in this work, by exploiting the concept of rough-fuzzy sets and generalising scale and move transformation-based fuzzy interpolation. A type-2 fuzzy set based interpolation approach is also presented as an alternative implementation of the framework. The effectiveness of this work in improving the robustness of fuzzy rule interpolation is demonstrated through the practical application to the prediction of disease rates in remote villages. Moreover, this framework is also further evaluated with application to other realistic decision making problems. The resultant accuracy reveals the efficacy of this research.

The number of applications of intelligent control systems has grown significantly over the last few decades, and today they are used in various challenging industrial application domains, where they provide particularly useful solutions. The term „intelligent controllers‟ describes a field where control approaches are represented by mechanisms similar to those used by the human brain. These characteristics include, for example, learning, modification, adaption, effective working with high levels of uncertainty and coping with large amounts of data. Intelligent control systems are particularly useful for complex systems such as biomedical and chemical plants, which are expected to work under optimal conditions. A good example of an intelligent controller is the so called Self-Organising Fuzzy Logic Control (SOFLC) proposed by Procyk and Mamdani in the late 1970s. The SOFLC scheme involves a control policy that allows its structure to be adapted based on the environment in which it operates. The SOFLC combines a conventional fuzzy logic controller with a supervisory layer which monitors and regulates the performance of the system. In this thesis, new architectures are proposed for single input single output (SISO) and multi-input multi- output (MIMO) structures to improve on the original SISO SOFLC design in terms of performance and robustness, as well as extend the analysis and design issues relating to such algorithms to the MIMO case using hybrid approaches. The work proposed in this thesis includes: 1. A new development of type-1 and type-2 Self-Organising Fuzzy Logic Control with a Dynamic Supervisory Layer (SOFLC-DSL) for the SISO case: In this part of the thesis, the work is mainly focused on designing a sophisticated SOFLC algorithm by combining a type-1 fuzzy system with a new Particle Swarm Optimisation (PSO) algorithm, so as to make the SOFLC scheme more flexible and effective in terms of responding to changes in the process to be controlled or the environment surrounding it. A new on-line PSO algorithm is developed by using the idea of credit assignment and fitness estimation to allow the optimisation of the consequent parts of the performance index (PI) table on-line. The proposed scheme is tested on a non-linear and uncertain Muscle Relaxation Model. Computer results demonstrate that the proposed algorithm achieve satisfactory performance, and is superior to the standard SOFLC scheme. In order to enhance the capabilities of the controller to deal with environments where the level of uncertainties and noise are high, both interval and zSlice type-2 fuzzy sets are deployed. Simulation results show that the performance of the SOFLC-DSL algorithm improves in terms of set-point tracking properties and the smoothness of the generated control signals. 2. A new extension of the SOFLC-DSL to the multivariable case: The proposed SOFLC-DSL algorithms are applied as the dominating controllers within multivariable control architectures. In order to deal with the effects of interactions between the input and output channels, both the relative array gain matrix as well as a linguistic switching mode compensator are considered. The proposed algorithms are tested on a drug dynamic process, and the results show they have good control abilities in terms of maintaining the desired set-points with smooth control effort, as well as in handling the interaction between different control channels.

The present thesis investigates the validity of some interesting principles such as the Axiom of Choice, AC, in the general extensional realizability structure V(A) for an arbitrary applicative structure, A, generalising the result by Rathjen established for the specific realizability model V(K_1), the Fan Theorem, FT, and the principle of Bar Induction, BI, in the particular realizability structures over the Graph Model, V(P(omega)), and over the Scott D1 Model, V(D_infty), since, in the literature, little is known about these realizability models and most investigations are carried out in the realizability models built over Kleene's first and second models. After an introduction and some background material, given in the first two chapters, I introduce the notion of extensional realizability over an arbitrary applicative structure, A, and I show that variants of the axiom of choice hold in V(A). Next, the focus switches from considering the general realizability structure V(A) generated on an arbitrary applicative structure, A, to the specific realizability universes, V(D_infty) and V(P(omega)) to investigate some interesting properties including the validity of FT and BI in these universes. For the remainder of the thesis, a proof of the soundness of realizability with truth, as it leads to different applications than that without truth, for the theories CZF and CZF + REA, is given and an investigation of many choice principles is carried out in the truth realizability universe V*(A) for an arbitrary applicative structure, A.

In this thesis we look at some properties of the local Turing Degrees, as a partial order. We first give discussion of the Turing Degrees and certain historical results, some translated into a form resembling the constructions we look at later. Chapter 1 gives a introduction to the Turing Degrees, Chapter 2 introduces the Local Degrees. In Chapter 3 we look at minimal Turing Degrees, modifying some historical results to use a priority tree, which we use in chapter 4 to prove the new result that every c.e. degree has the (minimal) meet property. Chapter 5 uses similar methods to establish existence of a high 2 degree that does not have the meet property.

The (outer) automorphism group of a finitely generated free group Fn, which we denote by Out(Fn), is a central object in the fields of geometric and combinatorial group theory. My thesis focuses on the study of the automorphism group of a free product of groups. As every finitely generated group can be written as a free product of finitely many freely indecomposable groups and a finitely generated free group (Grushko’s Theorem) it seems interesting to study the outer automorphism group of groups that split as a free product of simpler groups. Moreover, it turns out that many well known methods for the free case, can be used for the study of the outer automorphism group of such a free product. Recently, Out(Fn) is mainly studied via its action on a contractible space (which is called Culler - Vogtmann space or outer space and we denote it by CVn)and a natural asymmetric metric which is called the Lipschitz metric. More generally, similar objects exist for a general non-trivial free product. In particular, in this thesis we generalise theorems that are well known for CVn and Out(Fn) in the case of a finite free product, using the appropriate definitions and tools. Firstly, in [30], we generalise for an automorphism of a free product, a theorem due to Bestvina, Feighn and Handel, which states that the centraliser in Out(Fn) of an irreducible with irreducible powers automorphism of a free group is virtually infinite cyclic, where it is well known irreducible automorphisms form a (generic) class of automorphisms in the free case. In [31], we use the previous result in order to prove that the stabiliser of an attractive fixed point of an irreducible with irreducible powers automorphism in the relative boundary of a free product, can be computed. This was already well known for the free case and it is a result of Hilion. Finally, in [29] we prove that the Lipschitz metric for the general outer space is not even quasi-symmetric, but there is a ’nice’ function that bounds the asymmetry. As an application, we can see that this metric is quasi-symmetric if it is restricted on the thick part of outer space. The result in the free case is due to Algom-Kfir and Bestvina.

In this thesis, we consider questions relating to automorphisms and endomorphisms of countable, relational first-order structures M, with a particular emphasis on bimorphism monoids. We determine semigroup-theoretic results for three types of endomorphism monoid onM, along with generation results whenMis the random graph R or the discrete linear order (N;_). In addition, we introduce three types of partial map monoid ofM, and prove some semigroup-theoretic and generation results in these cases. We introduce the idea of a permutation monoid, and characterise the closed submonoids of the infinite symmetric group Sym(N). Following this, we turn our attention the idea of oligomorphic transformation monoids, and expand on the existing results by considering a range of notions of homomorphismhomogeneity as introduced by Lockett and Truss in 2012. Furthermore, we show that for any finite group G, there exists an oligomorphic permutation monoid with group of units isomorphic to G. The main result of the thesis is an analogue of Fra¨ıss´e’s theorem covering twelve of the eighteen notions of homomorphism-homogeneity; this contains both Fra¨ıss´e’s theorem, and a version of this for MM-homogeneous structures by Cameron and Neˇsetˇril in 2006, as corollaries. This is then used to determine the extent to which some well-known countable homogeneous structures are also homomorphism-homogeneous. Finally, we turn our attention to MB-homogeneous graphs and digraphs. We begin by classifying those homogeneous graphs that are also MB-homogeneous. We then determine an example of an MB-homogeneous graph not in this classification, and use the idea behind this construction to demonstrate 2@0 many non-isomorphic examples of MB-homogeneous graphs. We also give 2@0 many non-isomorphic examples of MB-homogeneous digraphs.

No description available.