bluuebunny/crossref_metadata_2025 huggingface dataset:
A Non-Interleaving Semantics for CCS Based on Proved Transitions
Authors: Boudol Gérard , Castellani Ilaria
Published: May 2021

When using labelled transition systems to model languages like CCS or TCSP, one specifies transitions by a set of structural rules. We consider labelling transitions with their proofs – in the given system of rules – instead of simple actions. Then the label of a transition identifies uniquely that transition, and one may use this information to define a concurrency relation on (proved) transitions, and a notion of residual of a (proved) transition by a concurrent one. We apply Berry and Lévy’s notion of equivalence by permutations to sequences of proved transitions for CCS to obtain a partial order semantics for this language.
ML-SMART: A Problem Solver for Learning from Examples
Authors: Bergadano F. , Gemello R. , Giordana A. , Saitta L.
Published: May 2021

This paper describes ML-SMART, a knowledge based system for inducing conceptual description from examples. It is organized as a problem solver and makes an integrated use of multiple search strategies, including characterization, constructive learning and deduction. The acquired knowledge consists of production rules organized into a network, which can be seen as a generalization of a decision tree. The condition part of the rules is expressed in a first order logic language also containing numerical quantification. The use of variables and functions allows highly structured concepts to be easily described. ML-SMART (Similarity-based Multiple-concept Acquisition and Reasoning Tool) is a domain independent system, provided with a friendly interface to ease the task of configuring a new application. It is well suited to work in noisy environments and has been tested in different domains for the sake of comparison with other existing systems.
An Equivalence of Communicating Processes in Distributed Environments
Authors: Winkowski Józef
Published: May 2021

The equivalence of communicating processes with respect to their external behaviour is formalized and studied. The processes are represented by mathematical systems related to labelled event structures. The equivalence is similar to the known observational equivalence but it is defined in a manner which reflects how processes behave in distributed environments. It is shown that the introduced equivalence is a congruence with respect to operations as in CCS (Milner’s Calculus of Communicating Systems).
A Good Normal Form for Relational Databases
Authors: Michalewicz Zbigniew , Yeo Alvin
Published: May 2021

In the conceptual design of relational databases one of the main goals is to create a conceptual scheme, which minimize redundancies and eliminate deletion and addition anomalies, i.e. to create relation schemes in some good normal form. The study of relational databases has produced a host of normal forms: 2NF, 3NF, BCNF, Elementary-Key Normal Form, 4NF, Weak 4NF, PJ/NF, DK/NF, LTKNF, (3,3)NF, etc. There are two features which characterize these normal forms. First, they consider each relation separately. We believe that a normal form (which reflects the goodness of the conceptual design) should be related to the whole conceptual scheme. Second, the usefullness of all normal forms in relational database design have been based on the assumption that a data definition language (DDL) of a database management system (DBMS) is able to enforce key dependencies. However, different DDLs have different capabilities in defining constraints. In this paper we will discuss the design of conceptual relational schemes in general. We will also define a good normal form (GNF) which requires a minimally rich DDL; this normal form is based only on a primitive concept of constraints. We will not, however, discuss the normalization process itself – how one might, if possible, convert a relation scheme that is not in some normal form into a collection of relation schemes each of which is in that normal form.
Parallel and Distributed Processability of Objects
Authors: Rine David C.
Published: May 2021

Partitioning and allocating of software components are two important parts of software design in distributed software engineering. This paper presents two general algorithms that can, to a limited extent, be used as tools to assist in partitioning software components represented as objects in a distributed software design environment. One algorithm produces a partition (equivalence classes) of the objects, and a second algorithm allows a minimum amount of redundancy. Only binary relationships of actions (use or non-use) are considered in this paper.
Topological Model Set Deformations in Logic Programming
Authors: Batarekh Aida , Subrahmanian V.S.
Published: May 2021

Given a first order language L, and a notion of a logic L w.r.t. L, we investigate the topological properties of the space of L-structures for L. We show that under a topology called the query topology which arises naturally in logic programming, the space of L-models (where L is a decent logic) of any sentence (set of clauses) in L may be regarded as a (closed, compact) T4-space. We then investigate the properties of maps from structures to structures. Our results allow us to apply various well-known results on the fixed-points of operators on topological spaces to the semantics of logic programming – in particular, we are able to derive necessary and sufficient topological conditions for the completion of covered general logic programs to be consistent. Moreover, we derive sufficient conditions guaranteeing the consistency of program completions, and for logic programs to be determinate. We also apply our results to characterize consistency of the unions of program completions.
Constructions of Grammars by Means of Reducing Operators
Authors: Novotný Miroslav
Published: May 2021

In [10] a reducing operator ρ was defined assigning a normed generalized grammar ρ(G) to any normed generalized grammar G in such a way that ρ(G) is in a certain sense less or equal to G and that both G and ρ(G) generate the same language. To any nontrivial language (V,L) a normed generalized grammar Gr(V,L) is assigned. Then ρ(Gr(V,L)) is proved to be a normed grammar if and only if (V,L) is a so called agreeable language.
Some Remarks on the Completed Database1
Authors: Kunen Kenneth
Published: May 2021

We show how Clark’s Completed Database (CDB) can be extended to include a number of Prolog constructs usually considered to be outside of pure logic, while still maintaining the known partial completeness results for SLDNF derivations. We also prove that in the semantics provided by the CDB and SLDNF, there is no definition of transitive closure which is strict and does not use function symbols.
A Process Specification Formalism1
Authors: Mauw S. , Veltink G.J.
Published: May 2021

Traditional methods for programming sequential machines are inadequate for specifying parallel systems. Because debugging of parallel programs is hard, due to e.g. non-deterministic execution, verification of program correctness becomes an even more important issue. The Algebra of Communicating Processes (ACP) is a formal theory which emphasizes verification and can be applied to a large domain of problems ranging from electronic circuits to CAM architectures. The manual verification of specifications of small size has already been achieved, but this cannot easily be extended to the verification of larger industrially relevant systems. To deal with this problem we need computer tools to help with the specification, simulation, verification and implementation. The first requirement for building such a set of tools is a specification language. In this paper we introduce PSFd (Process Specification Formalism – draft) which can be used to formally express processes in ACP. In order to meet the modern requirements of software engineering, like reusability of software, PSFd supports the modular construction of specifications and parameterization of modules. To be able to deal with the notion of data, ASF (Algebraic Specification Formalism) is embedded in our formalism. As semantics for PSFd a combination of initial algebra semantics and operational semantics for concurrent processes is used. A comparison with programming languages and other formal description techniques for the specification of concurrent systems is included.
Reducing Operators for Generalized Grammars
Authors: Novotný Miroslav
Published: May 2021

Theory of reducing operators elaborated for pure generalized grammars in [5] is transferred to normed generalized grammars. There exists a reducing operator ρ such that. for any normed generalized grammar G the normed generalized grammars G, ρ(G) generate the same languages; furthemore: ρ(G) is a normed grammar if and only if there exists a normed grammar G ′ such that G and G ′ generate the same language and G ′ is in a certain sense smaller than or equal to G. The reducing operator ρ is used to characterize the so called harmonic languages.
Resolution in the Domain of Strongly Finite Logics
Authors: Stachniak Zbigniew , O’Hearn Peter
Published: May 2021

In this paper the notion of a resolution counterpart of a propositional logic is introduced and studied. This notion is based on a generalization of the resolution rule of J.A. Robinson. It is shown that for every strongly finite logic a refutationally complete nonclausal resolution proof system can be constructed and that the completeness of such systems is preserved with respect to the polarity and set of support strategies.
Formalization of Inheritance Reasoning in Autoepistemic Logic
Authors: Gelfond Michael , Przymusinska Halina
Published: May 2021

Current research in the area of nonmonotonic reasoning suggests that autoepistemic logic provides a general framework for formalizing commonsense reasoning in various domains of discourse. The goal of this paper is to investigate the suitability of autoepistemic logic for formalization of some forms of inheritance reasoning. To this end we propose a new semantics for inheritance networks with exceptions based on autoepistemic logic.
Well-Founded Semantics Coincides with Three-Valued Stable Semantics1
Authors: Przymusinski Teodor
Published: May 2021

We introduce 3-valued stable models which are a natural generalization of standard (2-valued) stable models. We show that every logic program P has at least one 3-valued stable model and that the well-founded model of any program P [Van Gelder et al., 1990] coincides with the smallest 3-valued stable model of P. We conclude that the well-founded semantics of an arbitrary logic program coincides with the 3-valued stable model semantics. The 3-valued stable semantics is closely related to non-monotonic formalisms in AI. Namely, every program P can be translated into a suitable autoepistemic (resp. default) theory P ˆ so that the 3-valued stable semantics of P coincides with the (3-valued) autoepistemic (resp. default) semantics of P ˆ. Similar results hold for circumscription and CWA. Moreover, it can be shown that the 3-valued stable semantics has a natural extension to the class of all disjunctive logic programs and deductive databases. Finally, following upon the recent approach developed by Gelfond and Lifschitz, we extend all of our results to more general logic programs which, in addition to the use of negation as failure, permit the use of classical negation.
On the Classification and Existence of Structures in Default Logic1
Authors: Zhang Aidong , Marek Wiktor
Published: May 2021

We investigate possible belief sets of an agent reasoning with default rules. Besides of Reiter’s extensions which are based on a proof-theoretic paradigm (similar to Logic Programming), other structures for default theories, based on weaker or different methods of constructing belief sets are considered, in particular, weak extensions and minimal sets. The first of these concepts is known to be closely connected to autoepistemic expansions of Moore, the other to minimal stable autoepistemic theories containing the initial assumptions. We introduce the concept of stratifed collection of default rules and investigate the properties of the largest stratified subset of the family D, determined by W. We find a necessary and sufficient condition for a weak extension to be an extension in terms of stratification. We prove that for theories (D, W) without extension, the least fixed point of the associated operator (with weak extension or minimal set as a context) is an extension of suitably chosen (D’, W) with D’ ⊆ D. We investigate conditions for existence of extensions and introduce the notion of perfectly-stratified set of default rules and its variant of maximally perfectly-stratified set. Existence of such set of default rules turns out to be equivalent to the existence of extension. Finally, we investigate convergence of algorithm for computing extensions.
Vector Controlled Concurrent Systems, Part II: Comparisons
Authors: Keesmaat N.W. , Kleijn H.C.M. , Rozenberg G.
Published: May 2021

In this paper the behaviour of models of concurrent systems introduced in [KeeKleRoz] is investigated. In particular (i) static and dynamic models are compared and (ii) the effect of restricting the sequential components to be regular is considered.
Modelling Nondeterministic Concurrent Processes with Event Structures
Authors: Loogen Rita , Goltz Ursula
Published: May 2021

We present a non-interleaving model for non deterministic concurrent processes that is based on labelled event structures. We define operators on labelled event structures like parallel composition, nondeterministic combination, choice, prefixing and hiding. These operators correspond to the operations of the “Theory of Communicating Sequential Processes” (TCSP). Infinite processes are defined using the metric approach. The dynamic behaviour of event structures is defined by a transition relation which describes the execution of partially ordered sets of actions, abstracting from internal events.
On Uniqueness of the Wulff Shape for Cellular Automata
Authors: Wlaź Paweł
Published: May 2021

In this paper, ordered transition rules are investigated. Such rules describe an increment of mono-crystals and for every rule one can calculate so called Wulff Shape. It is shown that for some large class of these rules, there exists at most one growth function which generates a given Wulff Shape.
Diamond Properties of Elementary Net Systems
Authors: Hoogeboom Hendrik Jan , Rozenberg Grzegorz
Published: May 2021

An elementary net system is the basic system model of net theory. The state space of an elementary net system is formalized through the notion of the case graph, which is an edge-labeled graph with a distinguished initial node. The paper investigates syntactic, i.e., graph theoretic properties of case graphs of elementary net systems. In particular it studies the structure of isomorphisms between case graphs.
On Generalized Automata
Authors: Barua Rana
Published: May 2021

The usual notions of acceptance of automata acting on infinite strings yield sets that are in very low Borel classes. In response to a question by Landweber, Wiśniewski introduced the notion of generalized automata that yield sets at any specified level of the Borel hierachy. Here we show that most of Wiśniewski’s results can be easily derieved (and generalized) using the theory of positive analytical operations and δ – s operations.
Models of Clark’s Completion for Some Classes of Logic Programs
Authors: Baratella Stefano
Published: May 2021

Aim of this paper is to provide an alternative proof of consistency for the completion of a semi-strict program. Furthermore, we prove the continuity of the immediate consequence map associated to a locally call-consistent program with respect to any preinterpretation that is a model of the equality theory of its Clark’s completion.
Modal Nonmonotonic Logic with Restricted Application of the Negation as Failure to Prove Rule1
Authors: Truszczynski Mirosław
Published: May 2021

In the paper we study a family of modal nonmonotonic logics closely related to the family of modal nonmonotonic logics proposed by McDermott and Doyle. For a modal logic S and a fixed collection of formulas X we introduce the notion of an ( S, X)-expansion. We restrict to modal logics which have a complete Kripke semantics. We study the properties of ( S, X)-expansions and show that in many respects they are analogous to the properties of S-expansions in nonmonotonic modal logics of McDermott and Doyle.
Algebraic Theory of Independence in Information Systems
Authors: Novotný Miroslav , Pawlak Zdzizław
Published: May 2021

The semilattice of all subsets of a finite nonempty set provided with the operation of union and a congruence of this semilattice enable to define independent elements of the semilattice. Reducts, subreducts, and superreducts of an arbitrary element in the semilattice are introduced and investigated. A particular type of congruence, the so called rough top equality, is studied. These algebraic notions and methods are applied to black boxes, to information systems, and to contexts in Wille’s sense. The algebraic results are used to solve the problem whether two sets of inputs give the same output in a black box, whether two sets of attributes define the same classification of objects in an information system, and, finally, whether two sets of features generate the same concept in a context. Partial dependence between two sets of attributes of an information system is introduced and a distance between these sets is defined.
An Axiomatic Characterization of a Class of Petri Nets
Authors: Korczynski Waldemar
Published: May 2021

In this paper an algebraic characterization of a class of Petri nets is given. The nets are characterized by a kind of algebras, which can be considered as a generalization of the concept of the case graph of a (marked) Petri net.
An Algebraic Approach to the Approximation of Information
Authors: Comer Stephen D.
Published: May 2021

This paper is based on the notion of an information system  in the sense of Pawlak. Every set of knowledge P ⊆ Ω determines a closure operator on U. The class of Boolean algebras with added operations determined by all sets of know ledge are axiomatixed. As a consequence of the representation theorem information systems can be constructed that have a prescribed lattice of functional dependencies.
Reducts in Information Systems1
Authors: Rauszer Cecylia M.
Published: May 2021

In the paper we consider properties of minimal sets of attributes (reducts) which determine an equivalence relation ind(P). We show that the problem to figure out all reducts of a given set is NP-complete. Subsequently, we present some properties of the set of all attributes which are indispensable to create ind(P).
Deterministic Concurrent Systems
Authors: Hirshfeld Joram
Published: May 2021

We investigate possible ways to extend the notion of determinacy from automata to general concurrent systems (described here mainly as behavior structures).
A Modal Logic for Similarity Relations in Pawlak Knowledge Representation Systems
Authors: Vakarelov Dimiter
Published: May 2021

One of the main results of the paper is a characterization of certain kind similarity relations in Pawlak knowledge representation systems by means of first order sentences. As an application we obtain a complete finite axiomatization of the corresponding poly modal logic, called in the paper MLSim. It is proved that MLSim possesses finite model property and is decidable.
On Pure Context-Free Languages and Left Szilard Languages
Authors: Mäkinen Erkki
Published: May 2021

It is shown that left Szilard languages of context-free grammars are pure context-free languages. This is one of the few exceptions among the numerous negative results concerning the generative capacity of pure languages. Moreover, we characterize pure context-free languages and left Szilard languages of pure context-free grammars as certain homomorphic images.
A Problem on Easy Terms in λ-Calculus
Authors: Intrigila Benedetto
Published: May 2021

We say that a closed term M is easy in the λ β η-calculus if for every term N the theory λ β η + { M = N } is consistent. The main result of the paper is to show that, for a certain term P, the term P( ω ω) is easy, while P ω is not. It follows that the easiness of a given M does not imply either easiness or non-easiness of PM, contradicting an earlier conjecture.
Relational Chase Procedures Interpreted as Resolution with Paramodulation1
Authors: Biskup Joachim , Convent Bernhard
Published: May 2021

In this paper the relationship between dependency theory and first-order logic is explored in order to show how relational chase procedures (i.e., algorithms to decide inference problems for dependencies) can be interpreted as clever implementations of well known refutation procedures of first-order logic with resolution and paramodulation. On the one hand this alternative interpretation provides a deeper insight into the theoretical foundations of chase procedures, whereas on the other hand it makes available an already well established theory with a great amount of known results and techniques to be used for further investigations of the inference problem for dependencies. Our presentation is a detailed and careful elaboration of an idea formerly outlined by Grant and Jacobs which up to now seems to be disregarded by the database community although it definitely deserves more attention.
A Functionalization of Logical Kits
Authors: Wiweger Antoni
Published: May 2021

Relations between general logical kits and kits of some particular type, called functional kits, are investigated. The functional representation R(K) of a logical kit K is constructed and it is shown that R(K) is a reflection of K in the category of kits and A-surjective kit homomorphisms with respect to the subcategory of functional kits.
Many-Valued Modal Logics
Authors: Fitting Melvin C.
Published: May 2021

Two families of many-valued modal logics are investigated. Semantically, one family is characterized using Kripke models that allow formulas to take values in a finite many-valued logic, at each possible world. The second family generalizes this to allow the accessibility relation between worlds also to be many-valued. Gentzen sequent calculi are given for both versions, and soundness and completeness are established.
Quantification in Autoepistemic Logic
Authors: Konolige Kurt
Published: May 2021

Quantification in modal logic is interesting from a technical and philosophical standpoint. Here we look at quantification in autoepistemic logic, which is a modal logic of self-knowledge. We propose several different semantics, all based on the idea that having beliefs about an individual amounts to having a belief using a certain type of name for the individual.
Practical Tools for Reasoning About Linear Constraints
Authors: Huynh Tien , Joskowicz Leo , Lassez Catherine , Lassez Jean-Louis
Published: May 2021

We address the problem of building intelligent systems to reason about linear arithmetic constraints. We develop, along the lines of Logic Programming, a unifying framework based on the concept of Parametric Queries and a quasi-dual generalization of the classical Linear Programming optimization problem. Variable (quantifier) elimination is the key underlying operation which provides an oracle to answer all queries and plays a role similar to Resolution in Logic Programming. We discuss three methods for variable elimination, compare their feasibility, and establish their applicability. We then address practical issues of solvability and canonical representation, as well as dynamical updates and feedback. In particular, we show how the quasi-dual formulation can be used to achieve the discriminating characteristics of the classical Fourier algorithm regarding solvability, detection of implicit equalities and, in case of unsolvability, the detection of minimal unsolvable subsets. We illustrate the relevance of our approach with examples from the domain of spatial reasoning and demonstrate its viability with empirical results from two practical applications: computation of canonical forms and convex hull construction.
Query Processing in Distributed Information Systems
Authors: Ras Zbigniew W.
Published: May 2021

In our model of a distributed information system, two information structures are maintained – the application database and the (routing) database used to route queries in a computer network. Any site of a distributed information system which does not understand some attribute values used in a query has to search for a site which can explain them. The information stored in routing database has a strong impact on the speed of this search. In [5], we propose that each site learns from its neighbors the descriptions of all unknown attribute values used in queries. These descriptions are represented in the form of rules and stored in dictionaries added to all sites of a distributed information system. This extended distributed system with dictionaries is called intelligent.
On the Compactness Theorem of Propositional Temporal Logics
Authors: Leischner Martin
Published: May 2021

For a semantics SEM of a logical language L an associated semantics S E M ˆ is constructed by topological means such that the compactness theorem is true in S E M ˆ. The formulas in L, which are valid with respect to SEM, are identical to the formulas which are valid with respect to S E M ˆ. The concepts developed in the paper are illustrated by examples from the field of propositional temporal logics.
On the Generative Capacity of Context-Free Matrix Grammars over One-Letter Alphabet
Authors: Mäkinen Erkki
Published: May 2021

This note studies the conjecture that context-free matrix languages over one-letter alphabet are regular. We are able to confirm the conjecture in a special case where at most one non terminal can have an unbounded number of occurrences in sentential forms.
Partial Higher-Order Specifications1
Authors: Astesiano Egidio , Cerioli Maura
Published: May 2021

In this paper the classes of extensional models of higher-order partial conditional specifications are studied, with the emphasis on the closure properties of these classes. Further it is shown that any equationally complete inference system for partial conditional specifications may be extended to an inference system for partial higher-order conditional specifications, which is equationally complete w.r.t. the class of all extensional models. Then, applying some previous results, a deduction system is proposed, equationally complete for the class of extensional models of a partial conditional specification. Finally, turning the attention to the special important case of termextensional models, it is first shown a sound and equationally complete inference system and then necessary and sufficient conditions are given for the existence of free models, which are also free in the class of term-generated extensional models.
Notes on the Algebraic Approach to Dependence in Information Systems
Authors: Novotný Jiří , Novotný Miroslav
Published: May 2021

The concept of the relation of dependence between sets of attributes of an information system is studied in a more abstract setting – in the algebraic structure called dependence space. Complete characterization of dependence relation in a dependence space is presented.
On a Problem Concerning Dependence Spaces
Authors: Novotný Miroslav , Pawlak Zdzisław
Published: May 2021

A set Y of attributes of an information system is said to be dependent on a set X of attributes if the classification of objects defined by X is finer or as fine as the classification defined by Y. An important problem reads as follows. If Y depends on X find a minimal X ′ ⊆ X such that Y depends on X ′ . A set X ′ is said to be a reduct of X if X ′ is a minimal subset of X defining the same classification of objects as X. The paper is devoted to the study of relationship between reducts and dependence. Both dependence and reducts can be defined in the so called dependence spaces and the above mentioned problem can be transformed into the problem of constructing reducts in a suitable dependence space. We also present some algorithms providing reducts in a dependence space; in this way, we obtain an algorithmic solution of our problem.
A Representation of Partial Boolean Algebras
Authors: Ehrenfeucht Andrzej , Zawadowski Marek W.
Published: May 2021

We prove that every partial boolean algebra is isomorphic to a partial boolean algebra of sets. As a consequence we obtain finite axiomatization of the theory of partial boolean algebras.
Reasoning with Parsimonious and Moderately Grounded Expansions
Authors: Eiter Thomas , Gottlob Georg
Published: May 2021

We investigate the complexity of autoepistemic reasoning with parsimonious and moderately grounded expansions. A stable expansion of an autoepistemic set of premises is parsimonious if its objective (i.e. nonmodal) part does not contain the objective part of any other stable expansion. We prove that deciding whether a formula φ belongs to at least one parsimonious stable expansion of a finite base set A is complete for Σ 3 P , while deciding containment in all parsimonious stable expansions is complete for ∏ 3 P . Similar results are derived for autoepistemic reasoning with moderately grounded expansions. In particular, we show that deciding whether a formula φ belongs to some moderately grounded expansion of a finite base set A is Σ 3 P -complete, and that deciding whether φ belongs to all moderately grounded expansions is ∏ 3 P -complete. These results suggest that reasoning with parsimonious stable expansions and moderately grounded expansions is strictly harder than reasoning in Moore’s standard version of autoepistemic logic. We also address the complexity of reasoning if the set A is in a normalized form, and derive completeness results for this case.
On Perfect Introspection with Quantifying-In1
Authors: Lakemeyer Gerhard
Published: May 2021

Agents with perfect introspection may have incomplete beliefs about the world, but they possess complete knowledge about their own beliefs. This fact suggests that the beliefs of introspective agents should be completely determined by their objective beliefs, that is, those beliefs that are only about the domain in question and not about other beliefs. Introspection and logical reasoning alone should suffice to reconstruct all other beliefs from the objective ones. While this property has been shown to hold for propositional belief logics, there have so far only been negative results in the case of first-order belief logics with quantifying-in. In this paper we present a logic of belier with quantifying-in, where the beliefs of a perfectly introspective agent are indeed uniquely determined by the objective beliefs. The result is obtained by weakening the notion of belief of an existing logic that does not have this property.
Quality Criteria for Partial Order Semantics of Place/Transition-Nets with Capacities
Authors: Gold Robert , Vogler Walter
Published: May 2021

This paper discusses a number of properties that a partial order semantics should have in order to support the modular construction of nets and to deal with finite capacities. Characterizations for these properties are shown, and a new semantics is introduced which seems to be the natural choice if a certain set of properties is required.
Approximate Learning with Multiple Machines
Authors: Velauthapillai Mahendran
Published: May 2021

In this paper we define two new inference classes Team Density and Team Uniform Density. The team density class turns out to be the “most powerful” of all the inference classes that have been defined and studied so far. We compare these classes to previously defined classes. We obtain necessary and sufficient conditions for one team density class to be a subset of another team density class. Similar results are obtained for team uniform density class. We also have compare team density and team uniform density classes and obtained necessary and sufficient conditions for one class to be a subset of another. Most importantly we show that team density, the “most powerfull” class, cannot cover the BC class. From this result we obtain several theorems as corollaries that have been proved in earlier papers.
λ-Representability of Integer, Word and Tree Functions
Authors: Madry Małgorzata
Published: May 2021

Six λ-languages over function-types between algebras B, N and Υ are considered. Type N = ( 0 → 0 ) → ( 0 → 0 ) is called a non-negative integers type; B = ( 0 → 0 ) → ( ( 0 → 0 ) → ( 0 → 0 ) ) is called a binary words type; Υ = ( 0 → ( 0 → 0 ) ) → ( 0 → 0 ) is called a binary trees type. These associations come from the isomorphism between the types and corresponding algebraic structures. Closed terms whose types are the above mentioned function-types represent unary functions of appropriate types. The problem is: what class of functions is represented by the closed terms of the examined type. It is proved that for B → N, N → B, Υ → N, Υ → B there exists a finite base of functions such that any λ-definable function is some combination of the base functions. The algorithm which, for every closed term, returns the function in the form of a combination of the base functions is given. For two other types, B → Υ and N → Υ, a method of constructing λ-representable functions using primitive recursion is shown.
Logic as Programming
Authors: Van Benthem Johan
Published: May 2021

Starting from a general dynamic analysis of reasoning and programming, we develop two main dynamic perspectives upon logic programming. First, the standard fixed point semantics for Horn clause programs naturally supports imperative programming styles. Next, we provide axiomatizations for Prolog-type inference engines using calculi of sequents employing modified versions of standard structural rules such as monotonicity or permutation. Finally, we discuss the implications of all this for a broader enterprise of ‘abstract proof theory’.
Logical Characterization of Bounded Query Classes II: Polynomial-Time Oracle Machine
Authors: Stewart Iain A.
Published: May 2021

This paper continues an investigation into the expressibility of the logic (±HP)*[FOS]. In particular, we show that the logic (±HP)*[FOS] has the same expressibility as its sub-logic (±HP)1[FOS] which is known to capture the complexity class LNP (this class being those sets of strings accepted by some logspace deterministic oracle Turing machine with an oracle in NP). We consequently show that a naturally defined hierarchy within PNP collapses.
Ulam Games, Łukasiewicz Logic, and AF C*-Algebras
Authors: Mundici Daniele
Published: May 2021

Ulam asked what is the minimum number of yes-no questions necessary to find an unknown number in the search space (1, …, 2n), if up to l of the answers may be erroneous. The solutions to this problem provide optimal adaptive l error correcting codes. Traditional, nonadaptive l error correcting codes correspond to the particular case when all questions are formulated before all answers. We show that answers in Ulam’s game obey the (l+2)-valued logic of Łukasiewicz. Since approximately finite-dimensional (AF) C*-algebras can be interpreted in the infinite-valued sentential calculus, we discuss the relationship between game-theoretic notions and their C*-algebraic counterparts. We describe the correspondence between continuous trace AF C*-algebras, and Ulam games with separable Boolean search space S. whose questions are the clopen subspaces of S. We also show that these games correspond to finite products of countable Post MV algebras, as well as to countable lattice-ordered Specker groups with strong unit.
Deciding Clause Classes by Semantic Clash Resolution
Authors: Leitsch Alexander
Published: May 2021

It is investigated, how semantic clash resolution can be used to decide some classes of clause sets. Because semantic clash resolution is complete, the termination of the resolution procedure on a class Γ gives a decision procedure for Γ. Besides generalizing earlier results we investigate the relation between termination and clause complexity. For this purpose we define the general concept of atom complexity measure and show some general results about termination in terms of such measures. Moreover, rather than using fixed resolution refinements we define an algorithmic generator for decision procedures, which constructs appropriate semantic refinements out of the syntactical structure of the clause sets. This method is applied to the Bernays – Schönfinkel class, where it gives an efficient (resolution) decision procedure.
Application of a Rough Set-Based Inductive Learning System
Authors: Hadjimichael Michael , Wasilewska Anita
Published: May 2021

We present here an application of Rough Set formalism to Machine Learning. The resulting Inductive Learning algorithm is described, and its application to a set of real data is examined. The data consists of a survey of voter preferences taken during the 1988 presidential election in the U.S.A. Results include an analysis of the predictive accuracy of the generated rules, and an analysis of the semantic content of the rules.
Recognizable and Rational Subsets of Algebras
Authors: Steinby Magnus
Published: May 2021

In this paper recognizable and rational subsets of general algebras of finite type are studied. These are natural generalizations of the familiar notions originally defined for monoids, but they also include as special cases recognizable and rational tree languages, for example. Some closure properties of the families of recognizable and rational subsets are studied. The operations considered seem to be intimately connected with the recognizability and rationality properties of subsets, and they can also be defined for subsets of abstract algebras, regardless of the nature of the elements. The last part of the paper is devoted to generalized forms of Kleene’s theorem and related results.
Definability of Arithmetic Operations from the Order and a Random Relation1
Authors: Korec Ivan
Published: May 2021

For almost all binary relations R ⊆ N 2 the addition and multiplication on the set N of nonnegative integers (and hence all arithmetical relations) are first order definable in the structure (N; ⩽, R). The defining formulae can be chosen independently on R and the words “for almost all” mean “with probability 1” by a very natural probability measure.
Logic and Artificial Intelligence: A New Synthesis?1
Authors: Perlis Donald
Published: May 2021

There have been two major efforts at a synthesis of logic and artificial intelligence, one building on the other. I will review these and argue that yet another addition is needed.
Initial and Quasiinitial Models of Theories
Authors: Volger Hugo
Published: May 2021

We have shown earlier that the theories which uniformly admit initial families of models resp. disjoint initial families of models resp. initial models are exactly those which are closed under equalizers resp. equalizers and pullbacks (= connected limits) resp. equalizers and products (= arbitrary limits). In addition, syntactical characterizations had been given. To obtain an analogous result for pullbacks we have to weaken the initiality notions. Weakening the uniqueness of the morphism to a uniqueness up to an isomorphism we arrive at the corresponding quasiinitiality notions. As a new result we shall show that the theories which uniformly admit disjoint quasiinitial families of models resp. quasiinitial models are exactly those which are closed under pullbacks resp. pullbacks and products (= arbitrary limits). As a tool we use a localized version of initiality which was suggested by J.Adamek. Using our result Hébert recently obtained a syntactical characterization for the case of disjoint quasiinitial families. In the case of quasiinitial families the characterization by means of certain class of limit constructions is still an open problem.
Type Inference: Some Results, Some Problems1
Authors: Giannini Paola , Honsell Furio , Ronchi Della Rocca Simona
Published: May 2021

In this paper we investigate the type inference problem for a large class of type assignment systems for the λ-calculus. This is the problem of determining if a term has a type in a given system. We discuss, in particular, a collection of type assignment systems which correspond to the typed systems of Barendregt’s “cube”. Type dependencies being shown redundant, we focus on the strongest of all, Fω, the type assignment version of the system Fω of Girard. In order to manipulate uniformly type inferences we give a syntax directed presentation of Fω and introduce the notions of scheme and of principal type scheme. Making essential use of them, we succeed in reducing the type inference problem for Fω to a restriction of the higher order semi-unification problem and in showing that the conditional type inference problem for Fω is undecidable. Throughout the paper we call attention to open problems and formulate some conjectures.
On the Undecidability of Partial Polymorphic Type Reconstruction
Authors: Pfenning Frank
Published: May 2021

We prove that partial type reconstruction for the pure polymorphic λ-calculus is undecidable by a reduction from the second-order unification problem, extending a previous result by H.-J. Boehm. We show further that partial type reconstruction remains undecidable even in a very small predicative fragment of the polymorphic λ-calculus, which implies undecidability of partial type reconstruction for λ M L as introduced by Harper, Mitchell, and Moggi.
On a Framework for Logic Programming with Incomplete Information
Authors: Sakai Hiroshi
Published: May 2021

A framework for Logic Programming with Incomplete Information is proposed. Recently, an important problem has been much discussed in the field of knowledge bases, logic programming and AI, namely how effectively we use information which may have incompleteness, especially disjunctive information. In order to express disjunctive information, we use the predicate symbol orm, where the superscript m implies its arity, and as arguments we put every disjunctive information in orm, which we call an or-type atom. Based on or-type atoms, we define a new language called or-type language. Logic Program with Incomplete Information(LPII) is a subset of the or-type language. First, in a special case our framework is reduced to that of near-Horn prolog by Loveland and disjunctive logic programming by Minker. Then, we consider a general case, which is seen as an advancement from Lipski’s incomplete information system. In this case, we show the model intersection property, fixpoint theorem, the soundness and the completeness of a resolution which we call Box-resolution.
Retrieval System and Dynamic Algorithm Looking for Axioms of Notions Defined by Programs
Authors: Biela Andrzej
Published: May 2021

In this paper we shall introduce a formal system of algorithmic logic which enables us to formulate some problems connected with a retrieval system which provides a comprehensive tool in automated theorem proving of theorems consisting of programs, procedures and functions. The procedures and functions may occur in considered theorems while the program of the above mentioned system is being executed. We can get an answer whether some relations defined by programs hold and we can prove functional equations in a dynamic way by looking for a special set of axioms /assumptions/ during the execution of system. We formulate RS-algorithm which enables us to construct the set of axioms for proving some properties of functions and relations defined by programs. By RS-algorithm we get the dynamic process of proving functional equations and we can answer the question whether some relations defined by programs hold. It enables us to solve some problems concerning the correctness of programs. This system can be used for giving an expert appraisement. We shall provide the major structures and a sketch of an implementation of the above formal system.
Deletion Sets
Authors: Kari Lila , Mateescu Alexandru , Salomaa Arto , Păun Gheorghe
Published: May 2021

We discuss questions related to the cardinality, the effective construction, and decidability of the so-called deletion sets: the sets of strings obtained by erasing from a word the subwords which appear as elements of a given language.
The Syntax of Parallelism
Authors: Amir Amihood , Smith Carl H.
Published: May 2021

One of the problems associated with the introduction of parallel processors is the so called “dusty deck” problem. A solution entails the development of optimizing compilers that transform programs previously written for a conventional serial processor into functionally equivalent programs that exploit the parallel processing capabilities of the new multiprocessor machines. We introduce a function Composition Model that models parallel architectures as a hierarchy of syntactic function definitions. Position in the hierarchy is equivalent to parallel time complexity in the modelled architecture. Other parallel concepts such as global vs. local communications, concurrency or exclusivity of read and write, and the number of processors used in a computation, are modelled as well. We rigorously prove that a compiler that optimizes a program for parallelism on a CREW PRAM is not effectively computable, even if it is also given an optimal serial program for the same task and a time bounding function. It turns out that the function composition model is similar to some traditional models, such as the Grzegorczyk Hierarchy. Our parallel interpretation of the Grzegorczyk Hierarchy offers new insights and admits a new cleaner and more elegant definition of the hierarchy with a single base class, as opposed to Grzegorczyk’s three.
Time and Duration in Noninterleaving Concurrency
Authors: Murphy David
Published: May 2021

The purpose of this paper is to present a real-timed concurrency theory in the noninterleaving tradition. The theory is based on the occurrences of actions; each occurrence or event has a start and a finish. Causality is modelled by assigning a strict partial order to these starts and finishes, while timing is modelled by giving them reals. The theory is presented in some detail. All of the traditional notions found in concurrency theories (such as conflict, confusion, liveness, and so on) are found to be expressible. Four notions of causality arise naturally from the model, leading to notions of securing. Three of the notions give rise to underlying event structures, demonstrating that our model generalises Winskel’s. Infinite structures are then analysed: a poset of finite structures is defined and suitably completed to give one containing infinite structures. These infinite structures are characterised as just those arising as limits of finite ones. Our technique here, which relies on the structure of time, is of independent interest.
Two-Sided Strictly Locally Testable Languages
Authors: Holzer Markus , Kutrib Martin , Otto Friedrich
Published: May 2021

A two-sided extension of strictly locally testable languages is presented. In order to determine membership within a two-sided strictly locally testable language, the input must be scanned from both ends simultaneously, whereby it is synchronously checked that the factors read are correlated with respect to a given binary relation. The class of two-sided strictly locally testable languages is shown to be a proper subclass of the even linear languages that is incomparable to the regular languages with respect to inclusion. Furthermore, closure properties of the class of two-sided strictly locally testable languages and decision problems are studied. Finally, it is shown that two-sided strictly k-testable languages are learnable in the limit from positive data.
A Complete Taxonomy of Restarting Automata without Auxiliary Symbols*
Authors: Otto Friedrich
Published: May 2021

A complete taxonomy is presented for restarting automata without auxiliary symbols. In this taxonomy, the language classes that are accepted by deterministic and nondeterministic, monotone, weakly monotone, and non-monotone, shrinking and length-reducing restarting automata are compared to each other with respect to inclusion. As it turns out, the 45 types of restarting automata considered yield 29 different classes of languages. By presenting a collection of rather simple example languages, it is shown that, for any two of these language classes ℒ1 and ℒ2, the class ℒ1 is a subclass of ℒ2 if and only if ℒ1 is defined by a type of restarting automaton that is a restriction of a type of restarting automaton that defines the class ℒ2.