Wyniki wyszukiwania - BazTech

1

A model theory for the potential infinite

Eberl Matthias

Reports on Mathematical Logic

|

2022

|

Vol. 57

3--29

EN

We present the model theoretic concepts that allow mathematics to be developed with the notion of the potential infinite instead of the actual infinite. The potential infinite is understood as a dynamic notion, being an indefinitely extensible finite. The main adoption is the interpretation of the universal quantifier, which has an implicit reflection principle. Each universal quantification refers to an indefinitely large, but finite set. The quantified sets may increase, so after a reference by quantification, a further reference typically uses a larger, still finite set. We present the concepts for classical first-order logic and show that these dynamic models are sound and complete with respect to the usual inference rules. Moreover, a finite set of formulas requires a finite part of the increasing model for a correct interpretation.

2

Typology emerges from simplicity in representations and learning

Lambert Dakotah, Rawski Jonathan, Heinz Jeffrey

Journal of Language Modelling

|

2021

|

Vol. 9, No. 1

151--194

EN

We derive well-understood and well-studied subregular classes of formal languages purely from the computational perspective of algorithmic learning problems. We parameterise the learning problem along dimensions of representation and inference strategy. Of special interest are those classes of languages whose learning algorithms are necessarily not prohibitively expensive in space and time, since learners are often exposed to adverse conditions and sparse data. Learned natural language patterns are expected to be most like the patterns in these classes, an expectation supported by previous typological and linguistic research in phonology. A second result is that the learning algorithms presented here are completely agnostic to choice of linguistic representation. In the case of the subregular classes, the results fall out from traditional model-theoretic treatments of words and strings. The same learning algorithms, however, can be applied to model-theoretic treatments of other linguistic representations such as syntactic trees or autosegmental graphs, which opens a useful direction for future research.

3

Interpreted Graphs and ETPR(k) Graph Grammar Parsing for Syntactic Pattern Recognition

Flasiński M.

Machine Graphics and Vision

|

2018

|

Vol. 27, No. 1/4

3--19

EN

Further results of research into graph grammar parsing for syntactic pattern recognition (Pattern Recognit. 21:623-629, 1988; 23:765-774, 1990; 24:1223-1224, 1991; 26:1-16, 1993; 43:249-2264, 2010; Comput. Vision Graph. Image Process. 47:1-21, 1989; Fundam. Inform. 80:379-413, 2007; Theoret. Comp. Sci. 201:189-231, 1998) are presented in the paper. The notion of interpreted graphs based on Tarski's model theory is introduced. The bottom-up parsing algorithm for ETPR(k) graph grammars is defined.

4

Proving Nets Correct via Cause-Effect Structures (An Experiment)

Czaja L.

Fundamenta Informaticae

|

2003

|

Vol. 54, nr 2,3

165-183

EN

Proving safety and liveness of parallel systems is of unquestionable importance in system construction activity. A proof method for systems represented by nets (cause-effect structures and Petri nets) is proposed. Its outline is the following. (1) Let a problem specification as a formal theory i.e. a language system with specific relation symbols (operations, in particular), axioms and first-order inference rules be given. For each symbol introduce a class of atomic c-e structures (counterpart of Petri net transitions) to be the symbol's operational representative. (2) Using algebraic calculus of cause-effect structures, construct - from the atoms - a c-e structure and equivalent net intended to behave in accordance with the axioms (a mechanical step); (3) From the cause-effect structure just constructed, infer an algebraic structure and prove it to be a model (in terms of model theory) of the axiomatic system specifying the problem.

5

Institution-independent Ultraproducts

Diaconescu R.

Fundamenta Informaticae

|

2003

|

Vol. 55, nr 3,4

321-348

EN

We generalise the ultraproducts method from conventional model theory to an institution-independent (i.e. independent of the details of the actual logic formalised as an institution) framework based on a novel very general treatment of the semantics of some important concepts in logic, such as quantification, logical connectives, and ground atomic sentences. Unlike previous abstract model theoretic approaches to ultraproducts based on category theory, our work makes essential use of concepts central to institution theory, such as signature morphisms and model reducts. The institution-independent fundamental theorem on ultraproducts is presented in a modular manner, different combinations of its various parts giving different results in different logics or institutions. We present applications to institution-independent compactness, axiomatizability, and higher order sentences, and illustrate our concepts and results with examples from four different algebraic specification logics. In the introduction we also discuss the relevance of our institution-independent approach to the model theory of algebraic specification and computing science, but also to classical and abstract model theory.

6

J-energy preserving well-posed linear systems

Staffans O. J.

International Journal of Applied Mathematics and Computer Science

|

2001

|

Vol. 11, no 6

1361-1378

EN

The following is a short survey of the notion of a well-posed linear system. We start by describing the most basic concepts, proceed to discuss dissipative and conservative systems, and finally introduce J-energy-preserving systems, i.e., systems that preserve energy with respect to some generalized inner products (possibly semi-definite or indefinite) in the input, state and output spaces. The class of well-posed linear systems contains most linear time-independent distributed parameter systems: internal or boundary control of PDE's, integral equations, delay equations, etc. These systems have existed in an implicit form in the mathematics literature for a long time, and they are closely connected to the scattering theory by Lax and Phillips and to the model theory by Sz.-Nagy and Foias. The theory has been developed independently by many different schools, and it is only recently that these different approaches have begun to converge. One of the most interesting objects of the present study is the Riccati equation theory for this class of infinite-dimensional systems (H2- and Hinfty-theories).

7

A model-theoretic criterion for quantifier elimination and its application to geometry

Nowak K.

Bulletin of the Polish Academy of Sciences. Mathematics

|

1998

|

Vol. 46, no 4

377-381

EN

In this paper we present a model-theoretic criterion for quantifier elimination being a variant of Shoenfield's theorem (see [1], Chap. V, [paragraph]5). Our short proof is based directly on Godel's completeness and compactness theorems as well as on the concept of diagrams, and does not involve model-completeness or Robinson's test as does for instance the proof of certain related criteria given in [2], Chap. VIII, [paragraph]4. As a consequence, we immediately obtain the theorems of Chevalley and Tarski-Seidenberg from algebraic and semialalgebraic geometry.