No description available.

No description available.

A Hamilton cycle is a cycle which passes through every vertex of a graph. A Hamilton cycle decomposition of a k-regular graph is defined as the partition of the edge set into Hamilton cycles if k is even, or a partition into Hamilton cycles and a 1-factor, if k is odd. Consequently, for 2-regular or 3-regular graphs, finding a Hamilton cycle decompositon is equilvalent to finding a Hamilton cycle. Two classes of graphs are studies in this thesis and both have significant symmetry. The first class of graphs is the 6-regular circulant graphs. These are a king of Cayley graph. Given a finite group A and a subset S ⊆ A, the Cayley Graph Cay(A,S) is the simple graph with vertex set A and edge set {{a, as}|a ∈ A, s ∈ S}. If the group A is cyclic then the graph is called a circulant graph. This thesis proves two results on 6-regular circulant graphs: 1. There is a Hamilton cycle decomposition of every 6-regular circulant graph Cay(Z[subscript n],S) in which S has an element of order n; 2. There is a Hamilton cycle decomposition of every connected 6-regular circulant graph of odd order. The second class of graphs examined in this thesis is a futher generalization of the Generalized Petersen graphs. The Petersen graph is well known as a highly symmetrical graph which does not contain a Hamilton cycle. In 1983 Alspach completely determined which Generalized Petersen graphs contain Hamilton cycles. In this thesis we define a larger class of graphs which includes the Generalized Petersen graphs as a special case. We call this larger class spoked Cayley graphs. We determine which spoked Cayley graphs on Abelian groups are Hamiltonian. As a corollary, we determine which are 1-factorable.

Thesis (Ph. D.)--University of Wisconsin--Madison, 1982. / Typescript. Vita. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references (leaves 148-150).

This thesis examines two approaches to Galois correspondences in formal logic. A standard result of classical first-order model theory is the observation that models of L-theories with a weak form of elimination of imaginaries hold a correspondence between their substructures and automorphism groups defined on them. This work applies the resultant framework to explore the practical consequences of a model-theoretic Galois theory with respect to certain first-order L-theories. The framework is also used to motivate an examination of its underlying model-theoretic foundations. The model-theoretic Galois theory of pure fields and valued fields is compared to the algebraic Galois theory of pure and valued fields to point out differences that may hold between them. The framework of this logical Galois correspondence is also applied to the theory of pseudoexponentiation to obtain a sketch of the Galois theory of exponential fields, where the fixed substructure of the complex pseudoexponential field B is an exponential field with the field Qrab as its algebraic subfield. This work obtains a partial exponential analogue to the Kronecker-Weber theorem by describing the pure field-theoretic abelian extensions of Qrab, expanding upon work in the twelfth of Hilbert’s problems. This result is then used to determine some of the model-theoretic abelian extensions of the fixed substructure of B. This work also incorporates the principles required of this model-theoretic framework in order to develop a model theory over substructural logics which is capable of expressing this Galois correspondence. A formal semantics is developed for quantified predicate substructural logics based on algebraic models for their propositional or nonquantified fragments. This semantics is then used to develop substructural forms of standard results in classical first-order model theory. This work then uses this substructural model theory to demonstrate the Galois correspondence that substructural first-order theories can carry in certain situations.

A suitable subcategory of affine Azumaya algebras is defined and a functor from this category to the category of Zariski structures is constructed. The rudiments of a theory of presheaves of topological structures is developed and applied to construct examples of structures at a generic parameter. The category of equivariant algebras is defined and a first-order theory is associated to each object. For those theories satisfying a certain technical condition, uncountable categoricity and quantifier elimination results are established. Models are shown to be Zariski structures and a functor from the category of equivariant algebras to Zariski structures is constructed. The two functors obtained in the thesis are shown to agree on a nontrivial class of algebras.

In concurrency theory—the branch of (theoretical) computer science that studies the logical and mathematical foundations of parallel computation—there are two main formal ways of modelling the behaviour of systems where multiple actions or events can happen independently and at the same time: either with interleaving or with partial order semantics. On the one hand, the interleaving semantics approach proposes to reduce concurrency to the nondeterministic, sequential computation of the events the system can perform independently. On the other hand, partial order semantics represent concurrency explicitly by means of an independence relation on the set of events that the system can execute in parallel; following this approach, the so-called ‘true concurrency’ approach, independence or concurrency is a primitive notion rather than a derived concept as in the interleaving framework. Using interleaving or partial order semantics is, however, more than a matter of taste. In fact, choosing one kind of semantics over the other can have important implications—both from theoretical and practical viewpoints—as making such a choice can raise different issues, some of which we investigate here. More specifically, this thesis studies concurrent systems with partial order semantics and focuses on their bisimulation and model-checking problems; the theories and techniques herein apply, in a uniform way, to different classes of Petri nets, event structures, and transition system with independence (TSI) models. Some results of this work are: a number of mu-calculi (in this case, fixpoint extensions of modal logic) that, in certain classes of systems, induce exactly the same identifications as some of the standard bisimulation equivalences used in concurrency. Secondly, the introduction of (infinite) higher-order logic games for bisimulation and for model-checking, where the players of the games are given (local) monadic second-order power on the sets of elements they are allowed to play. And, finally, the formalization of a new order-theoretic concurrent game model that provides a uniform approach to bisimulation and model-checking and bridges some mathematical concepts in order theory with the more operational world of games. In particular, we show that in all cases the logic games for bisimulation and model-checking developed in this thesis are sound and complete, and therefore, also determined—even when considering models of infinite state systems; moreover, these logic games are decidable in the finite case and underpin novel decision procedures for systems verification. Since the mu-calculi and (infinite) logic games studied here generalise well-known fixpoint modal logics as well as game-theoretic decision procedures for analysing concurrent systems with interleaving semantics, this thesis provides some of the groundwork for the design of a logic-based, game-theoretic framework for studying, in a uniform manner, several concurrent systems regardless of whether they have an interleaving or a partial order semantics.

We describe contributions to algorithmic proof techniques for deciding the satisfiability of boolean combinations of many-variable nonlinear polynomial equations and inequalities over the real and complex numbers. In the first half, we present an abstract theory of Grobner basis construction algorithms for algebraically closed fields of characteristic zero and use it to introduce and prove the correctness of Grobner basis methods tailored to the needs of modern satisfiability modulo theories (SMT) solvers. In the process, we use the technique of proof orders to derive a generalisation of S-polynomial superfluousness in terms of transfinite induction along an ordinal parameterised by a monomial order. We use this generalisation to prove the abstract (“strategy-independent”) admissibility of a number of superfluous S-polynomial criteria important for efficient basis construction. Finally, we consider local notions of proof minimality for weak Nullstellensatz proofs and give ideal-theoretic methods for computing complex “unsatisfiable cores” which contribute to efficient SMT solving in the context of nonlinear complex arithmetic. In the second half, we consider the problem of effectively combining a heterogeneous collection of decision techniques for fragments of the existential theory of real closed fields. We propose and investigate a number of novel combined decision methods and implement them in our proof tool RAHD (Real Algebra in High Dimensions). We build a hierarchy of increasingly powerful combined decision methods, culminating in a generalisation of partial cylindrical algebraic decomposition (CAD) which we call Abstract Partial CAD. This generalisation incorporates the use of arbitrary sound but possibly incomplete proof procedures for the existential theory of real closed fields as first-class functional parameters for “short-circuiting” expensive computations during the lifting phase of CAD. Identifying these proof procedure parameters formally with RAHD proof strategies, we implement the method in RAHD for the case of full-dimensional cell decompositions and investigate its efficacy with respect to the Brown-McCallum projection operator. We end with some wishes for the future.

According to the classical consistency presupposition, contradictions have an explosive character: Whenever they are present in a theory, anything goes, and no sensible reasoning can thus take place. A logic is paraconsistent if it disallows such presupposition, and allows instead for some inconsistent yet non-trivial theories to make perfect sense. The Logics of Formal Inconsistency, LFIs, form a particularly expressive class of paraconsistent logics in which the metatheoretical notion of consistency can be internalized at the object-language level. As a consequence, the LFIs are able to recapture consistent reasoning by the addition of appropriate consistency assumptions. The present monograph introduces the LFIs and provides several illustrations of them and of their properties, showing that such logics constitute in fact the majority of interesting paraconsistent systems in the literature. Several ways of performing the recapture of consistent reasoning inside such inconsistent systems are also illustrated. In each case, interpretations in terms of many-valued, possible-translations, or modal semantics are provided, and the problems related to providing algebraic counterparts to such logics are surveyed. A formal abstract approach is proposed to all related definitions and an extended investigation is made into the logical principles and the positive and negative properties of negation.

In this thesis, the notion of the derivation spaces is introduced. In a suitable two-sorted language, the first order theory of these structures is studied. In particular, it is shown that the theory is not companionable. In the last section, the language is expanded by predicate symbols for a dependence relation. In this language it is shown that the extension of the corresponding theory has a model companion. It is shown that the model companion is a complete, unstable theory which does not eliminate quantifiers.