This thesis deals with reachability and freeness problems for systems with linear dynamics, including hybrid systems and matrix semigroups. Hybrid systems are a type of dynamical system that exhibit both continuous and discrete dynamic behaviour. Thus they are particularly useful in modelling practical real world systems which can both flow (continuous behaviour) and jump (discrete behaviour). Decision questions for matrix semigroups have attracted a great deal of attention in both the Mathematics and Theoretical Computer Science communities. They can also be used to model applications with only discrete components. For a computational model, the reachability problem asks whether we can reach a target point starting from an initial point, which is a natural question both in theoretical study and for real-world applications. By studying this problem and its variations, we shall prove in a formal mathematical sense that many problems are intractable or even unsolvable. Thus we know when such a problem appears in other areas like Biology, Physics or Chemistry, either the problem itself needs to be simplified, or it should by studied by approximation. In this thesis we concentrate on a specific hybrid system model, called an HPCD, and its variations. The objective of studying this model is twofold: to obtain the most expressive system for which reachability is algorithmically solvable and to explore the simplest system for which it is impossible to solve. For the solvable sub-cases, we shall also study whether reachability is in some sense easy or hard by determining which complexity classes the problem belongs to, such as P, NP(-hard) and PSPACE(-hard). Some undecidable results for matrix semigroups are also shown, which both strengthen our knowledge of the structure of matrix semigroups, and lead to some undecidability results for other models.

The first part of the thesis studies invariant subspaces of strictly singular operators. By a celebrated result of Aronszajn and Smith, every compact operator has an invariant subspace. There are two classes of operators which are close to compact operators: strictly singular and finitely strictly singular operators. Pelczynski asked whether every strictly singular operator has an invariant subspace. This question was answered by Read in the negative. We answer the same question for finitely strictly singular operators, also in the negative. We also study Schreier singular operators. We show that this subclass of strictly singular operators is closed under multiplication by bounded operators. In addition, we find some sufficient conditions for a product of Schreier singular operators to be compact. The second part studies almost invariant subspaces. A subspace Y of a Banach space is almost invariant under an operator T if TY is a subspace of Y+F for some finite-dimensional subspace F ("error"). Almost invariant subspaces of weighted shift operators are investigated. We also study almost invariant subspaces of algebras of operators. We establish that if an algebra is norm closed then the dimensions of "errors" for the operators in the algebra are uniformly bounded. We obtain that under certain conditions, if an algebra of operators has an almost invariant subspace then it also has an invariant subspace. Also, we study the question of whether an algebra and its closure have the same almost invariant subspaces. The last two parts study collections of positive operators (including positive matrices) and their invariant subspaces. A version of Lomonosov theorem about dual algebras is obtained for collections of positive operators. Properties of indecomposable (i.e., having no common invariant order ideals) semigroups of nonnegative matrices are studied. It is shown that the "smallness" (in various senses) of some entries of matrices in an indecomposable semigroup of positive matrices implies the "smallness" of the entire semigroup. / Mathematics

No description available.

A semigroup is simply a set with an associative binary operation; computational semigroup theory is the branch of mathematics concerned with developing techniques for computing with semigroups, as well as investigating semigroups with the help of computers. This thesis explores both sides of computational semigroup theory, across several topics, especially in the finite case. The central focus of this thesis is computing and describing maximal subsemigroups of finite semigroups. A maximal subsemigroup of a semigroup is a proper subsemigroup that is contained in no other proper subsemigroup. We present novel and useful algorithms for computing the maximal subsemigroups of an arbitrary finite semigroup, building on the paper of Graham, Graham, and Rhodes from 1968. In certain cases, the algorithms reduce to computing maximal subgroups of finite groups, and analysing graphs that capture information about the regular I-classes of a semigroup. We use the framework underpinning these algorithms to describe the maximal subsemigroups of many families of finite transformation and diagram monoids. This reproduces and greatly extends a large amount of existing work in the literature, and allows us to easily see the common features between these maximal subsemigroups. This thesis is also concerned with direct products of semigroups, and with a special class of semigroups known as Rees 0-matrix semigroups. We extend known results concerning the generating sets of direct products of semigroups; in doing so, we propose techniques for computing relatively small generating sets for certain kinds of direct products. Additionally, we characterise several features of Rees 0-matrix semigroups in terms of their underlying semigroups and matrices, such as their Green's relations and generating sets, and whether they are inverse. In doing so, we suggest new methods for computing Rees 0-matrix semigroups.