Search

We consider finite models of the first group of Hilbert's axioms of the Euclidean geometry (the so-called axioms of incidence). We give a lower bound on the number of such models with n points, and we calculate their exact number for n up to 12. [ABSTRACT FROM AUTHOR]

The research entails a finite-element design of a 3d-autopilot missile synthesis of multiple objective controls by solving the inequalities encountered while using a linear matrix. The autopilot design analyses the performance methodologies for a group of finite models that are further linearised at different aerodynamic roll angles within the flight coverage for harnessing the uncertainties that are encountered confined within the high angle-of-attack region. Multiple simulation results are devised at various roll angle conditions to satisfy the performance of the controls. [ABSTRACT FROM AUTHOR]

We introduce a restricted second-order logic |$\textrm{SO}^{\textit{plog}}$| for finite structures where second-order quantification ranges over relations of size at most poly-logarithmic in the size of the structure. We demonstrate the relevance of this logic and complexity class by several problems in database theory. We then prove a Fagin's style theorem showing that the Boolean queries which can be expressed in the existential fragment of |$\textrm{SO}^{\textit{plog}}$| correspond exactly to the class of decision problems that can be computed by a non-deterministic Turing machine with random access to the input in time |$O((\log n)^k)$| for some |$k \ge 0$|⁠ , i.e. to the class of problems computable in non-deterministic poly-logarithmic time. It should be noted that unlike Fagin's theorem which proves that the existential fragment of second-order logic captures NP over arbitrary finite structures, our result only holds over ordered finite structures, since |$\textrm{SO}^{\textit{plog}}$| is too weak as to define a total order of the domain. Nevertheless, |$\textrm{SO}^{\textit{plog}}$| provides natural levels of expressibility within poly-logarithmic space in a way which is closely related to how second-order logic provides natural levels of expressibility within polynomial space. Indeed, we show an exact correspondence between the quantifier prefix classes of |$\textrm{SO}^{\textit{plog}}$| and the levels of the non-deterministic poly-logarithmic time hierarchy, analogous to the correspondence between the quantifier prefix classes of second-order logic and the polynomial-time hierarchy. Our work closely relates to the constant depth quasipolynomial size AND/OR circuits and corresponding restricted second-order logic defined by David A. Mix Barrington in 1992. We explore this relationship in detail. [ABSTRACT FROM AUTHOR]

The research entails a finite-element design of a 3d-autopilot missile synthesis of multiple objective controls by solving the inequalities encountered while using a linear matrix. The autopilot design analyses the performance methodologies for a group of finite models that are further linearised at different aerodynamic roll angles within the flight coverage for harnessing the uncertainties that are encountered confined within the high angle-of-attack region. Multiple simulation results are devised at various roll angle conditions to satisfy the performance of the controls.

The property of being true in almost all finite, initial segments of the standard model of arithmetic is ∑20 -complete. Thus, it admits a kind of a truth definition. We define such an arithmetical predicate. Then, we define its modal logic SL and prove a completeness theorem with respect to finite models semantics. The proof that SL is the modal logic of the approximate truth definition for finite arithmetical models is based on an extension of SL by a fixed-point construction. [ABSTRACT FROM AUTHOR]

The main contribution of this paper is is updating a nonlinear discriminant function on the basis of data of unknown origin. Specifically a procedure is developed for updating the nonlinear discriminant function on the basis of two Burr Type III distributions (TBIIID) when the additional observations are mixed or classified. First the nonlinear discriminant function of the assumed model is obtained. Then the total probabilities of misclassification are calculated. In addition a Monte carlo simulation runs are used to compute the relative efficiencies in order to investigate the performance of the developed updating procedures. Finally the results obtained in this paper are illustrated through a real and simulated data set. [ABSTRACT FROM PUBLISHER]

This paper starts with an explanation of how the logicist research program can be approached within the framework of Leśniewski's systems. One nice feature of the system is that Hume's Principle is derivable in it from an explicit definition of natural numbers. I generalize this result to show that all predicative abstraction principles corresponding to second-level relations, which are provably equivalence relations, are provable. However, the system fails, despite being much neater than the construction of Principia Mathematica (PM). One of the key reasons is that, just as in the case of the system of PM, without the assumption that infinitely many objects exist, (renderings of) most of the standard axioms of Peano Arithmetic are not derivable in the system. I prove that introducing modal quantifiers meant to capture the intuitions behind potential infinity results in the (renderings of) axioms of Peano Arithmetic (PA) being valid in all relational models (i.e. Kripke-style models, to be defined later on) of the extended language. The second, historical part of the paper contains a user-friendly description of Leśniewski's own arithmetic and a brief investigation into its properties. [ABSTRACT FROM AUTHOR]

Optical models of the human eye have been used in visual science for purposes such as providing a framework for explaining optical phenomena in vision, for predicting how refraction and aberrations are affected by change in ocular biometry and as computational tools for exploring the limitations imposed on vision by the optical system of the eye. We address the issue of what is understood by optical model eyes, discussing the 'encyclopaedia' and 'toy train' approaches to modelling. An extensive list of purposes of models is provided. We discuss many of the theoretical types of optical models (also schematic eyes) of varying anatomical accuracy, including single, three and four refracting surface variants. We cover the models with lens structure in the form of nested shells and gradient index. Many optical eye models give accurate predictions only for small angles and small fields of view. If aberrations and image quality are important to consider, such 'paraxial' model eyes must be replaced by 'finite model' eyes incorporating features such as aspheric surfaces, tilts and decentrations, wavelength-dependent media and curved retinas. Many optical model eyes are population averages and must become adaptable to account for age, gender, ethnicity, refractive error and accommodation. They can also be customised for the individual when extensive ocular biometry and optical performance data are available. We consider which optical model should be used for a particular purpose, adhering to the principle that the best model is the simplest fit for the task. We provide a glimpse into the future of optical models of the human eye. This review is interwoven with historical developments, highlighting the important people who have contributed so richly to our understanding of visual optics. [ABSTRACT FROM AUTHOR]

We consider sl-semantics in which first order sentences are interpreted in potentially infinite domains. A potentially infinite domain is a growing sequence of finite models. We prove the completeness theorem for first order logic under this semantics. Additionally we characterize the logic of such domains as having a learnable, but not recursive, set of axioms. The work is a part of author's research devoted to computationally motivated foundations of mathematics. [ABSTRACT FROM AUTHOR]

By a celebrated theorem of Morley, a theory T is ℵ1-categorical if and only if it is κ-categorical for all uncountable κ. In this paper we are taking the first steps towards extending Morley's categoricity theorem 'to the finite'. In more detail, we are presenting conditions, implying that certain finite subsets of certain ℵ1-categorical T have at most one n-element model for each natural number [ABSTRACT FROM AUTHOR]

An important class of problems in combinatorics is to find orthogonal latin squares with certain properties. Computer search is a promising approach for solving such problems. But generally its worst-case complexity is high. This paper describes how to use a general-purpose model searching program to find orthogonal latin squares. New techniques for problem representation and symmetry breaking are proposed to increase search efficiency. [ABSTRACT FROM AUTHOR]

We consider the notion of everyday language. We claim that everyday language is semantically bounded by the properties expressible in the existential fragment of second-order logic. Two arguments for this thesis are formulated. First, we show that Barwise's so-called test of negation normality works properly only when assuming our main thesis. Second, we discuss the argument from practical computability for finite universes. Everyday language sentences are directly or indirectly verifiable. We show that in both cases they are bounded by second-order existential properties. Moreover, there are known examples of everyday language sentences that are the most difficult in this class (NPTIME-complete). [ABSTRACT FROM AUTHOR]

Abstract: We investigate families of finite initial segments of standard models for various arithmetics. We give an axiomatization of the theory of sentences true in almost all finite models with addition. We also characterize its complete extensions and relate its infinite models to models of Presburger arithmetic. We also estimate the complexity of complete extensions of the arithmetic with addition and multiplication. [Copyright &y& Elsevier]

In interactive theorem proving practice a significant amount of time is spent on unsuccessful proof attempts of wrong conjectures. An automatic method that reveals them by generating finite counter examples would offer an extremely valuable support for a proof engineer by saving his time and effort. In practice, such counter examples tend to be small, so usually there is no need to search for big instances. Most definitions of functions or predicates on infinite structures do not preserve the semantics if a transition to arbitrary finite substructures is made. We propose constraints which guarantee a correct axiomatization on finite structures and present an approach which uses the Alloy Analyzer to generate finite instances of theories in the theorem prover KIV. It is evaluated on the library of basic data types as well as on some challenging case studies in KIV. The technique is implemented using the Kodkod constraint solver which is a successor of Alloy. [ABSTRACT FROM AUTHOR]

We consider a discrete time Markov Decision Process (MDP) under the discounted payoff criterion in the presence of additional discounted cost constraints. We study the sensitivity of optimal Stationary Randomized (SR) policies in this setting with respect to the upper bound on the discounted cost constraint functionals. We show that such sensitivity analysis leads to an improved version of the Feinberg–Shwartz algorithm (Math Oper Res 21(4):922–945, 1996) for finding optimal policies that are ultimately stationary and deterministic. [ABSTRACT FROM AUTHOR]

A probability distribution can be given to the set of isomorphism classes of models with universe {1, ..., n} of a sentence in first-order logic. We study the entropy of this distribution and derive a result from the 0–1 law for first-order sentences. [ABSTRACT FROM AUTHOR]

The paper presents the current state of knowledge in the field of logical investigations of finite arithmetics. This is an attempt to summarize the ideas and results in this area. Some new results are presented – these are mainly generalizations of the earlier results related to properties of sl-theories and some nontrivial cases of FM-representability theorem. [ABSTRACT FROM AUTHOR]

Abstract: In recent years, a tight connection has emerged between modal logic on the one hand and coalgebras, understood as generic transition systems, on the other hand. Here, we prove that (finitary) coalgebraic modal logic has the finite model property. This fact not only reproves known completeness results for coalgebraic modal logic, which we push further by establishing that every coalgebraic modal logic admits a complete axiomatisation in rank 1; it also enables us to establish a generic decidability result and a first complexity bound. Examples covered by these general results include, besides standard Hennessy–Milner logic, graded modal logic and probabilistic modal logic. [Copyright &y& Elsevier]

In this paper, it is the first time ever to suggest that we study the model theory of all finite structures and to put the equal sign in the same situtation as the other relations. Using formulas of infinite lengths we obtain new theorems for the preservation of model extensions, submodels, model homomorphisms and inverse homomorphisms. These kinds of theorems were discussed in Chang and Keisler's Model Theory, systematically for general models, but Gurevich obtained some different theorems in this direction for finite models. In our paper the old theorems manage to survive in the finite model theory. There are some differences between into homomorphisms and onto homomorphisms in preservation theorems too. We also study reduced models and minimum models. The characterization sentence of a model is given, which derives a general result for any theory T to be equivalent to a set of existential-universal sentences. Some results about completeness and model completeness are also given. [ABSTRACT FROM AUTHOR]

Ash's functions Nσ ,k count the number of k -equivalence classes of σ -structures of size n . Some conditions on their asymptotic behavior imply the long standing spectrum conjecture. We present a new condition which is equivalent to this conjecture and we discriminate some easy and difficult particular cases. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

We consider first order modal logic C firstly defined by Carnap in “Meaning and Necessity” [1]. We prove elimination of nested modalities for this logic, which gives additionally the Skolem-Löwenheim theorem for C. We also evaluate the degree of unsolvability for C, by showing that it is exactly 0′. We compare this logic with the logics of Henkin quantifiers, Σ11 logic, and SO. We also shortly discuss properties of the logic C in finite models. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

We prove that there exists a constant k such that for every n ⩾ 1 there exists a directed core graph Hn with at least 2n vertices such that a directed graph G is Hn-colorable if and only if every subgraph of G with at most kn log(n) vertices is Hn-colorable. Our examples show that in general the "duals of relational structures" in the sense of [J. Nešetřil and C. Tardif, J. Combin. Theory Ser. B, 80 (2000), pp. 80-97] can have superpolynomial size. The construction given in this paper gives a double exponential upper bound for such a construction. Here we improve this to an exponential upper bound. [ABSTRACT FROM AUTHOR]

We investigate theories of initial segments of the standard models for arithmetics. It is easy to see that if the ordering relation is definable in the standard model then the decid ability results can be transferred from the infinite model into the finite models. On the contrary we show that the σ2-theory of multiplication is undecidable in finite models. We show that this result is optimal by proving that the σ2-theory of multiplication and order is decidable in finite models as well as in the standard model. We show also that the exponentiation function is definable in finite models by a formula of arithmetic with multiplication and that one can define in finite models the arithmetic of addition and multiplication with the concatenation operation. We consider also the spectrum problem. We show that the spectrum of arithmetic with multiplication and arithmetic with exponentiation is strictly contained in the spectrum of arithmetic with addition and multiplication. [ABSTRACT FROM AUTHOR]

The nominalistic ontology of Kotarbinski, Slupecki and Tarski does not provide any direct interpretations of the sets of higher types which play important roles in type theory and in set theory. For this and other reasons (to be explained below) I will interpret those theories as descriptions of some finite structures which are actually constructed in human imaginations and stored in their memories. Those structures will be described (mathematically defined) in this lecture. They are hinted by the idea of Skolem functions and Hilbert''s ϵ-symbols, and they constitute a finitistic modification of Tarski''s concept of a model. They suggest also a form of the evolutionary process which leads to the development of human intelligence and language. [Copyright &y& Elsevier]

For every nondeterministic Turing machine M of time complexity T(n), there is a second-order sentence σ of a very restricted form, whose set of finite models encodes the set of strings recognized by M. Specifically, σ has a relational symbol which is interpreted as addition restricted to finite segments of the natural numbers, and a prefix consisting of existentially quantified unary second-order variables followed by a universal-existential first-order part. Here, every input string x is encoded by a model of size T(|x|). Using a closely related encoding of strings as models where the size of the model is the length of the string, a consequence is that if T(n)= n, then there is a sentence with a similar prefix but whose second-order variables are d-ary and whose finite models encode the strings accepted by M. Potential applications to low-level complexity are discussed. [ABSTRACT FROM AUTHOR]

We prove the finite model property (fmp) for BCI and BCI with additive conjunction, which answers some open questions in Meyer and Ono [11]. We also obtain similar results for some restricted versions of these systems in the style of the Lambek calculus [10, 3]. The key tool is the method of barriers which was earlier introduced by the author to prove fmp for the product-free Lambek calculus [2] and the commutative product-free Lambek calculus [4]. [ABSTRACT FROM AUTHOR]