A proof-theoretic metatheorem for tracial von Neumann algebras

We adapt a continuous logic axiomatization of tracial von Neumann algebras due to Farah, Hart and Sherman in order to prove a metatheorem for this class of structures in the style of proof mining, a research programme that aims to obtain the hidden computational content of ordinary mathematical proofs using tools from proof theory.     

Bounded linear-time temporal logic: A proof-theoretic investigation

Propositional and first-order bounded linear-time temporal logics (BLTL and FBLTL, respectively) are introduced by restricting Gentzen type sequent calculi for linear-time temporal logics. The corresponding Robinson type resolution calculi, RC and FRC for BLTL and FBLTL respectively are obtained. To prove the equivalence between FRC and FBLTL, a temporal version of Herbrand theorem is used. The completeness theorems for BLTL and FBLTL are proved for simple semantics with both a bounded time domain and some bounded valuation conditions on temporal operators. The cut-elimination theorems for BLTL and FBLTL are also proved using some theorems for embedding BLTL and FBLTL into propositional (first-order, respectively) classical logic. Although FBLTL is undecidable, its monadic fragment is shown to be decidable.     

Multicomponent proof-theoretic method for proving interpolation properties

Proof-theoretic method has been successfully used almost from the inception of interpolation properties to provide efficient constructive proofs thereof. Until recently, the method was limited to sequent calculi (and their notational variants), despite the richness of generalizations of sequent structures developed in structural proof theory in the meantime. In this paper, we provide a systematic and uniform account of the recent extension of this proof-theoretic method to hypersequents, nested sequents, and labelled sequents for normal modal logic. The method is presented in terms and notation easily adaptable to other similar formalisms, and interpolant transformations are stated for typical rule types rather than for individual rules.     

Normal forms for fuzzy logics: a proof-theoretic approach

A method is described for obtaining conjunctive normal forms for logics using Gentzen-style rules possessing a special kind of strong invertibility. This method is then applied to a number of prominent fuzzy logics using hypersequent rules adapted from calculi defined in the literature. In particular, a normal form with simple McNaughton functions as literals is generated for ?ukasiewicz logic, and normal forms with simple implicational formulas as literals are obtained for Gödel logic, Product logic, and Cancellative hoop logic.     

Computability-theoretic and proof-theoretic aspects of partial and linear orderings

Szpilrajn’s Theorem states that any partial orderP=〈S,<p〉 has a linear extensionP=〈S,<L〉. This is a central result in the theory of partial orderings, allowing one to define, for instance, the dimension of a partial ordering. It is now natural to ask questions like “Does a well-partial ordering always have a well-ordered linear extension?” Variations of Szpilrajn’s Theorem state, for various (but not for all) linear order typesτ, that ifP does not contain a subchain of order typeτ, then we can chooseL so thatL also does not contain a subchain of order typeτ. In particular, a well-partial ordering always has a well-ordered extension.We show that several effective versions of variations of Szpilrajn’s Theorem fail, and use this to narrow down their proof-theoretic strength in the spirit of reverse mathematics.     

A collection formula

A table of partially ordered sets, corresponding to the basis commutators (in Hall's sense) of weight 9, is given. On the basis of this table, the exponents in the collection formula can be found by elementary combinatorial methods. An example is given.Translated from Zapiski Nauchnykh Seminarov Leningardskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 46, pp. 59–63, 1974.     

A collection of subgroups for the generalized Burnside ring

In this paper, we will introduce a new collection of subgroups; which induces a generalized Burnside ring. This collection arises from the normalizers of certain p-radical subgroups.     

A note on the schemes of replacement and collection

We derive the schemes of from certain weak forms of the same.     

ARC A computerized system for urban garbage collection

Summary In this paper we present ARC a computerized system developed for urban garbage collection. The package is intended to help the planners in the design of efficient collection routes and to facilitate the study and evaluation of alternatives concerning issues such as the type and number of vehicles, frequency of collection and type and location of refuse containers. The final product is a “user friendly” system designed to be used by the planners without outside assistance. Work partially supported by grant PB 86-0310 of CICYT.     

A collection of examples where Neville elimination outperforms Gaussian elimination

Neville elimination is an elimination procedure alternative to Gaussian elimination. It is very useful when dealing with totally positive matrices, for which nice stability results are known. Here we include examples, most of them test matrices used in MATLAB which are not totally positive matrices, where Neville elimination outperforms Gaussian elimination.     

Theory and application of perceptual positions to data collection and analysis in military environments

We describe a novel approach to planning and interpretation of data collection activities in military environments, based on the notions of perceptual positions of self, other and detached observer when viewing the same event. We have reinterpreted the results of previous field experiments involving the introduction of advanced equipment as part of soldier modernisation and believe that we now have a better understanding of why some attempts at data collection were not as successful as others. We propose a protocol based on the Army Practitioner providing first position data (subjective), the Analyst Observer and instrumentation providing third position data (objective) and the Subject Matter Adviser giving second position data (speculative). Although there is often a focus on first and third position data during field trials, second position data enables extrapolation to other contexts. This is especially important for exploratory studies investigating future concepts. Taken together, the combination of the three positions leads to a better strategy to enhance data collection of complex military systems.     

A note on effective ultrapowers: Uniform failure of bounded collection

By suitably adapting an argument of Hirschfeld (see [2, Chapter 9]), we show that there is a single Δ₁ formula that defeats “bounded collection” for any model of II₂ Arithmetic that is either a recursive ultrapower or an existentially complete model. Some related facts are noted. MSC: 03F30, 03C62.     

A constant-factor approximation algorithm for multi-vehicle collection for processing problem

We define the multiple-vehicle collection for processing problem (mCfPP) as a vehicle routing and scheduling problem in which items that accumulate at customer sites over time should be transferred by a series of tours to a processing facility. We show that this problem with the makespan objective (mCfPP( $C_{\max }$ )) is NP-hard using an approximation preserving reduction from a two-stage, hybrid flowshop scheduling problem. We develop a polynomial-time, constant-factor approximation algorithm to solve mCfPP( $C_{\max }$ ). The problem with a single site is analyzed as a special case with two purposes. First, we identify the minimum number of vehicles required to achieve a lower bound on the makespan, and second, we characterize the optimal makespan when a single vehicle is utilized.     

A graphic construction of the collection formula for certain types of groups

Procedures for calculating P. Hall's famous collection formula for metabelian and two types of transmetabelian groups are described. Complicated combinatorial calculations are based on graphs corresponding to basic monomials. In conclusion programs written in PASCAL are given.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademiya Nauk SSSR, Vol. 191, pp. 140–151, 1991.