bluuebunny/crossref_metadata_2025 huggingface dataset:
Some Properties of Trace Languages
Authors: Rytter Wojciech
Published: May 2021

In this paper we present an application of nondeterministic multihead automata to the membership problem for trace languages. Here our result shows that regular and context-free trace languages are not very complicated. On the other hand, we make two simple observations which are the evidence that regular trace languages are very complicated from the algebraic point of view.
On the Connectivity of the Product of Automata
Authors: Bavel Zamir , Grzymała-Busse Jerzy , Soo Hong Kwang
Published: May 2021

Our main results include: Sufficient conditions for two strongly connected automata to have a strongly connected product. Sufficient conditions for the product of two connected automata to be connected and sufficient conditions for it to be not connected. Necessary and sufficient conditions for the product of two strongly connected automata, one of which is total, to be strongly connected. Necessary and sufficient conditions that a singly-generated subautomaton of the product be strongly connected. Necessary and sufficient conditions for the existence of an isomorphic copy of an automaton in its product with another.
On Local Control and Conflict Resolution in Petri Nets
Authors: Burkhard Hens-Dieter
Published: May 2021

A certain partition of transitions in Petri Nets is characterized. This partition makes possible to construct local control which excludes global conflict.
Modalities for Total Correctness
Authors: Farinas del Cerro Luis
Published: May 2021

This paper is concerned with the relationship of termination problem for regular programs to the validity of certain formulas in modal logic.
On Sequential Form of Functional Dynamic Logics
Authors: Pliuškevičius Regimantas
Published: May 2021

A Gentzen-style axiomatization of dynamic logics is proposed. It is compared to other axiom systems for dynamic logics. Some problems of relative decidability are considered.
On P – Normal Form of Parallel Program
Authors: Stapp Lucjan
Published: May 2021

In the last few years parallel programs are intensively studied. But when parallel program is investigated, it is assumed, that only one “cobegin … coend” (“fork … join”) operation is used (see e.g. [1,2]) in the program schemata. In the paper we introduce the notion of the equivalence relation between parallel programs and then it is proved that it is sufficient to study properties of parallel programs only with one “cobegin … coend” program connective.
A Note on the Impact of Conflict Resolution to Liveness and Deadlock in Petri Nets
Authors: Burkhard Hans-Dieter , Starke Peter H.
Published: May 2021

In this paper systems are investigated which consist of a Petri net and a control device. In any situation of the systems the control device selects one (or some) of the (concurrently) enabled transitions of the net and orders them to fire – this way solving conflicts, avoiding deadlocks etc. The results concern the corresponding decidability problems and the question whether it is possible to carry over such properties as deadlock avoidance and liveness from the uncontrolled net to a controlled net and vice versa.
On Some Subset of the Partition Set
Authors: Grzymała-Busse Jerzy W. , Pawlak Zdzisław
Published: May 2021

This paper contains a simple algorithm for minimal partition of a set, which is the departure point to study attribute dependencies in information system (see [3], [6], [7], [9]). Theoretical properties of such partitions have been studied by Łoś (see [5]) and the proposed algorithm has been implemented by Stevens (see [8]). The implementation shows many practical advantages of the proposed method.
Equivalence Relations in Classes of Stochastic Automata
Authors: Janicki Sławomir
Published: May 2021

Bartoszyński raised and investigated problems of extensions and shrinkages of the Markov chain type stochastic automata (Some remarks on extensions of stochastic automata, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 18(1970), 551–556). By such an automaton we mean an ordered triple ⟨T, α, A⟩, where T denotes a finite non-empty set, α is a function from T to [0, 1] with ∑ t ∈ T α ( t ) = 1, and A is a function T×T → [0, 1] with ∑ t ∈ T A ( s , t ) = 1 for every s ∈ T. If an extension (shrinkage) of two automata exists, then we say that they satisfy the relation Re(Rs). The aim of this paper is to consider some classes of automate with the same set T in which the relations Re and Rs are equivalence relations. We consider also some other relations in the class of stochastic automata. Moreover, in the first part we deal with extensions and shrinkages of probability measures.
On Pseudo-Random Sequences over Finite Automata
Authors: Kramosil Ivan
Published: May 2021

It is a well-known fact that binary sequences (strings) of high algorithmic complexity can be taken as good approximations of statistically independent random sequences with two equiprobable outputs. Here “sequence of high algorithmic complexity” is such one, that the length of the shortest program generating this sequence by a universal Turing machine differs only by an a priori given constant from the length of the generated sequence. The present paper generalizes this result to the case of a finite (not necessarily binary) alphabet. Considering an infinite sequence of finite sequences of high algorithmic complexity over a finite alphabet, the relative frequency of occurences of each letter or finite string of letters is proved to tend to the inverted value of the total number of letters, or strings of letters of the given length, in question. This result may be seen as an analogy to the strong law of large numbers in the case of equiprobable probability distribution.
Nondeterministic Programs Definable in Typed λ-Calculus
Authors: Zaionc Marek
Published: May 2021

In this paper term grammars are introduced. The expressing power of this grammars with variables of natural number type are just the nondeterministic programs built up without composition but with iteration of extended polynomials.
Rough Grammars
Authors: Kierczak Janusz
Published: May 2021

In the paper we define the notions of the best lower and the best upper approximations of grammar, which are based on the concept of rough set introduced by Pawlak in [4]. Furthermore we give the properties of languages generated by the best lower and the best upper approximations of grammar.
Semiconditional Contextual Grammars
Authors: Păun Gheorghe
Published: May 2021

One defines a class of contextual grammars “intermediate” between the conditional contextual grammars and the contextual grammars with bounded choice (the addition of each context depends on a prefix and a suffix of the current string which belong to a given pair of languages associated with this context). The paper investigates the generative capacity of these grammars compared to other contextual language families and with families in Chomsky hierarchy.
Structures Determined by Properties of Finite Families of Algorithms
Authors: Dańko Wiktor
Published: May 2021

In the paper the following problem stated by Tajtslin in 1979 is investigated: Let A = ⟨ A; f1, …, fn; r1, …, rm ⟩ be a structure. Are there functions f′1, …, f′p and relations r′1, …, r′q definable in A by means of algorithms such that every function relation definable over A by an algorithm is first-order definable in A + = ⟨ A; f1, …, fn, f′1, …, f′p; r1, …, rm, r′1, …, r′q⟩?
On Generalized Vector Space Model in Information Retrieval
Authors: Wong S.K.M. , Ziarko Wojciech
Published: May 2021

In information retrieval, it is common to model index terms and documents as vectors in a suitably defined vector space. The main difficulty with this approach is that the explicit representation of term vectors is not known a priori. For this reason, the vector space model adopted by Salton for the SMART system treats the terms as a set of orthogonal vectors. In such a model it is often necessary to adopt a separate, corrective procedure to take into account the correlations between terms. In this paper, we propose a systematic method (the generalized vector space model) to compute term correlations directly from automatic indexing scheme. We also demonstrate how such correlations can be included with minimal modification in the existing vector based information retrieval systems.
Categorical Models for Handshaking Communications1
Authors: Labella Anna , Pettorossi Alberto
Published: May 2021

Various languages, formalisms and algebraic structures have been recently proposed for denoting parallel computations and communications among processes. As in [LaP 83] we restrict our attention to the CCS [Mil 80] and CSP [Hoa 78] languages. We provide categorical models for their basic constructs and operations. The parallel composition and other kinds of interactions among computing processes will be interpreted as categorical constructions in suitable categories.
Finite Automata on Transfinite Sequences and Regular Expressions
Authors: Wojciechowski Jerzy
Published: May 2021

In this paper the notion of regular expression for finite automata on transfinite sequences /TF-automata/ is introduced. The characterization theorem for TF-automata is proved. From this theorem we conclude the decidability of the emptiness problem for TF-automata and the characterization theorem for finite automata on transfinite sequences of bounded lenght.
Fair Termination with Cruel Schedulers
Authors: Dayan Ido , Harel David
Published: May 2021

The problem of transforming nondeterministic or concurrent programs involving fairness assumptions into fairness-free schedulers is considered. The availability of such transformations provides an indirect way of proving fair termination. Building upon a general tree-transformation result of Harel, and scheduler-yielding transformations of devised by several researchers, we provide a general way of finding such transformations for a very broad class of fairness criteria. In passing, we explicitly construct a scheduler for Pnueli’s rather elusive notion of extreme fairness. Our schedulers are really nondeterministic, and may be termed “cruel” since they leave choices to the program, but immediately thereafter cause it to abort if it happens to make the wrong choice.
Logical Decision Problems and Complexity of Logic Programs
Authors: Börger Egon , Löwen Ulrich
Published: May 2021

We survey and give new results on logical characterizations of complexity classes in terms of the computational complexity of decision problems of various classes of logical formulas. There are two main approaches to obtain such results: The first approach yields logical descriptions of complexity classes by semantic restrictions (to e.g. finite structures) together with syntactic enrichment of logic by new expressive means (like e.g. fixed point operators). The second approach characterizes complexity classes by (the decision problem of) classes of formulas determined by purely syntactic restrictions on the formation of formulas.
A Unified Model in Information Retrieval1
Authors: Wong S.K.M. , Ziarko Wojciech
Published: May 2021

We introduce a new information retrieval model, the generalized vector space model (GVSM). In the GVSM, Boolean-like queries can be transformed into vectors spanned by the atoms of the free Boolean algebra generated by the index terms. Documents can, therefore, be ranked with respect to a query as in the conventional vector space model. Most significantly, the GVSM provides a unified view of the Boolean retrieval and vector-processing systems.
A Coin-Weighing Problem and Its Connection with the Security of a Statistical Database
Authors: Michalewicz Zbigniew
Published: May 2021

We consider the problem of compromisability of a statistical database. This paper is an attempt to evaluate the implications of using “yes-no” queries instead of the usual statistical queries; for this purpose we solve a certain coin-weighing problem.
Decision Expression Optimization1
Authors: Cockett J.R.B.
Published: May 2021

A basic concern when using decision trees for the solution of taxonomic or similar problems is their efficiency. Often the information that is required to completely optimize a tree is simply not available. This is especially the case when a criterion based on probabilities is used. It is shown how it is often possible, despite the absence of this information, to improve the design of the tree. The approach is based on algebraic methods for manipulating decision trees and the identification of some particularly desirable forms.
Deterministic Context-Free Dynamic Logic Is More Expressive than Deterministic Dynamic Logic of Regular Programs1
Authors: Urzyczyn Pawel
Published: May 2021

We show an example of an algebra T∙, such that every flow-chart program is equivalent in T∙ to a loop-free approximation of itself, while a program augmented by one binary push-down store is not equivalent in T∙ to any loop-free program. From this we deduce that the Deterministic Dynamic Logic of regular programs is strictly weaker than the Deterministic Context-Free Dynamic Logic.
Fair Derivations in Logic Programming: Operational and Greatest Fixpoint Semantics
Authors: Nait Abdallah Mohand-Areski
Published: May 2021

Using topological methods, we study the operational and greatest fixpoint semantics of infinite computations in logic programming. We show the equivalence of the operational and greatest fix point semantics in the case of fair derivations. We give some canonical partition, and soundness and completeness results which generalize already known results about the finitary case. Since fair derivations are a generalization of successful derivations, we thus give a uniform treatment of all meaningful computations in logic programming.
The Regular Expression Descriptions of Unifier Set in the Typed λ-Calculus
Authors: Zaionc Marec
Published: May 2021

λ-language over simple type structure is considered. We investigate unification problem such that number of elementary substitutions in a potentially infinite matching tree introduced by Huet is finite (compare [8]). The substitutions are generated using term grammar technique. Such a grammar consists of productions which are on the form; nonterminal variable of certain type produces a term of the same type. The most interesting is the case when matching tree is infinite and includes an infinite number of most general unifiers. We will show an interesting property of the infinite unification trees from examined class: for every infinite branch there is a node which occurs earlier in this tree. It means that there are some fragments which are repeated in this tree. Therefore the set of most general unifiers which are represented by terminal nodes can be described by regular expression over finite alphabet. Regular expression are constructed as a solution of linear language equalities. For every problem from this class the set of unifiers is described by some language. This language can be approximated by regular languages.
Unique Decipherability for Partially Commutative Alphabets
Authors: Chrobak Marek , Rytter Wojciech
Published: May 2021

We consider the unique decipherability problem for partially commutative alphabets. It is shown that the decidability of the problem depends heavily on the size of the alphabet and the structure of the graph of the commutativity relation. In particular, for alphabets with at most three letters the problem is decidable and for alphabets of bigger size the problem is undecidable.
Logics of Programs with Boolean Memory
Authors: Urzyczyn Pawel
Published: May 2021

We discuss the computational power of programs with boolean (propositional) push-down stores and arrays, and the expressive power of logics based on these programs. In particular we show that over unary structures, the mentioned logics occur to be equivalent to their “algebraic counterparts.
Multiranges and Multitrackers in Statistical Databases
Authors: Michalewicz Zbigniew , Yeo Anthony
Published: May 2021

The goal of statistical databases is to provide statistics about groups of individuals while protecting their privacy. Sometimes. by correlating enough statistics, sensitive data about individual can be inferred. The problem of protecting against such indirect disclosures of confidential data is called the inference problem and a protecting mechanism – an inference control. A good inference control mechanism should be effective (it should provide security to a reasonable extent) and feasible (a practical way exists to enforce it). At the same time it should retain the richness of the information revealed to the users. During the last few years several techniques were developed for controlling inferences. One of the earliest inference controls for statistical databases restricts the responses computed over too small or too large query-sets. However, this technique is easily subverted. In this paper we propose a new query-set size inference control which is based on the idea of multiranges and has better performance then the original one.
Towards the Temporal Approach to Abstract Data Types
Authors: Szalas Andrzej
Published: May 2021

In this paper we deal with a well known problem of specifying abstract data types. Up to now there were many approaches to this problem. We follow the axiomatic style of specifying abstract data types (cf. e.g. [1, 2, 6, 8, 9, 10]). We apply, however, the first-order temporal logic. We introduce a notion of first-order completeness of axiomatic specifications and show a general method for obtaining first-order complete axiomatizations. Some examples illustrate the method.
A Complexity Theoretic Parade of Network-Flow-Problems
Authors: Meinel Christoph
Published: May 2021

In the following we prove the p-projection completeness of a number of extremely restricted modifications of the NETWORK-FLOW-PROBLEM for such well known nonuniform complexity classes like NC1, L, NL, co- NL, P, NP using a branching-program based characterization of these classes given in [Ba86] and [Me86a,b].
Constructing Delaunay Triangulations by Merging Buckets in Quad Tree Order
Authors: Katajainen Jyrki , Koppinen Markku
Published: May 2021

Recently Rex Dwyer [D87] presented an algorithm which constructs a Delaunay triangulation for a planar set of N sites in O(N log log N) expected time and O(N log N) worst-case time. We show that a slight modification of his algorithm preserves the worst-case running time, but has only O(N) average running time. The methcxl is a hybrid which combines the cell technique with the divide-and-conquer algorithm of Guibas & Stolfi [GS85]. First a square grid of size about N by N is placed on the set of sites. The grid forms about N cells (buckets), each of which is implemented as a list of the sites which fall into the corresponding square of the grid. A Delaunay triangulation of the generally rather few sites within each cell is constructed with the Guibas & Stolfi algorithm. Then the triangulations are merged, four by four, in a quadtree-like order.
Compositional Semantics of Pure Place/Transition Systems1
Authors: Mazurkiewicz Antoni
Published: May 2021

The notion of synchronization of qualified pomsets (pomsets equipped with an alphabet) is introduced and some properties of this operation are given. It is claimed that the synchronization operation is a sufficient tool for composing complex concurrent systems from a set of simple atomic ones. As an example the behaviour of pure place/transition Petri nets is defined by means of qualified pomset synchronization.
Behavior Structures and Nets
Authors: Rabinovich A. , Trakhtenbrot B.A.
Published: May 2021

Behavior Structures integrate causality and branching. Nets of Behavior Structures provide a unifying approach to different net models of Concurrency. The Theory is illustrated wrt Nets over automata in particular wrt Petri Nets.
Event Structure Representation of the Behaviour of Place/Transition Systems
Authors: Winkowski Józef
Published: May 2021

It is shown how the nonsequential behaviour of marked Petri nets of places and transitions can be described with the aid of mathematical systems related to labelled event structures. The method of description is modular in the sense that the global behaviour is obtained by combining local ones corresponding lo places and transitions.
Dynamic Hierarchical Dependency
Authors: Chen Keh-Hsun
Published: May 2021

In this paper, a new kind of dependencies for databases, called dynamic hierarchical dependencies (DH-dependencies), is proposed and studied. DH-dependencies naturally suit DH-databases, which are based on Sandwall’s dynamic data hierarchy structure. An efficient inference algorithm on DH-dependencies is proposed and its correctness is proved. Information retrieval with DH-dependencies is investigated.
Algebraic Operations on Restricted Cardinality Sets in Relational Databases
Authors: Michalewicz Zbigniew , Groves Lindsay
Published: May 2021

A number of approaches have been taken to incorporating sets in relational databases. We review three such approaches and discuss a new approach, called restricted cardinality sets, which combines aspects of the other approaches, allowing both compound values and incomplete information to be represented. We show that this approach generalizes the other approaches, leading to a simpler, more flexible representation; and discuss the definition of algebraic operations on such sets.
Learning Concept Descriptions in a Growing Language
Authors: Ras Zbigniew W. , Zemankova Mafia
Published: May 2021

Humans are capable of producing compact high-level concept descriptions built from previously known concepts and attribute values. In the method presented here, initially concepts are described in terms of attribute values. These descriptions are in a probabilistic DNF form. Assuming a growing language, concepts already known to the system can be used in describing new concepts. The order of teaching the concepts is the key to producing their optimal descriptions. By “optimal” we mean the minimum number of occurrences of constants in descriptions. The problem of finding the minimal description for each concept is NP-complete, hence our proposed algorithm has to be heuristic. Our strategy is based on clustering terms in concept descriptions in order to replace them by shorter higher level terms. Results of the algorithm are optimized concepts descriptions in terms of a growing language, and a concept network that can be used for further learning and reasoning within the concept knowledge base.
On Temporal Logic for Distributed Systems and Its Application to Processes Communicating by Interrupts
Authors: Szalas Andrzej , Petermann Uwe
Published: May 2021

We present a temporal logic suitable for axiomatic specification of properties of distributed systems. The temporal logic considered is first-order with atnext operators interpreted as local modalities. Its semantics, different from those provided in other approaches, does not rely on a succesor relation in a set of global states, and mirrors the nature of distributed computations. The logic introduced is applied to axiomatization of a process communication scheme based on sending and handling interrupts.
On the Construction of Optimal Time Adders
Authors: Becker Bernd , Kolla Reiner
Published: May 2021

In this paper we present the design of a novel optimal time adder: the conditional carry adder. In order to perform addition a tree-like combination of multiplexer cells is used in the carry computation part. We show that, for the complete conditional carry adder, this results in an overall computation time which seems to be substantially shorter than for any other known (optimal time) adder (e.g. carry look ahead adders ([5]) or conditional sum adders ([12])). The second part of this paper contains a uniform approach to the computation of the carry function resulting in seven different classes of optimal time adders. It is shown that the conditional carry adder and the carry look ahead adder are representatives of two different classes. While section 1 defines the conditional carry adder and proposes a realization which is very time efficient, section 2 provides the possibility to compare this choice with other possible realizations and to choose a different design depending e.g. on specific properties of a given technology.
Negation as Failure to Prove and Fixed Points
Authors: Marek W. , Truszczynski M.
Published: May 2021

We investigate solutions of fixed point equations related to the negation as “failure to prove” rule, and show their relevance to minimal models.
Two Applications of Model-Theoretic Forcing to Lipski’s Data Bases with Incomplete Information1
Authors: Suchenek Marek A.
Published: May 2021

This paper concerns two aspects of incomplete information in data bases: - computations of answers to queries which are externally interpreted in some incomplete first-order structures with dependencies, and - the proper treatment of modal operators in such structures. We introduce the notion of an incomplete first-order structure with dependencies which seems to be an adequate model of data bases with incomplete information. We show that the widely accepted implicit assumption that first-order models (of a data base) have a unique domain, has no first-order consequences if the set of premises (represented in the data base) contains only a finite amount of information explicitly involving the elements of this domain. This observation allows us to evaluate the degree of unsolvability of the problem of answering externally interpreted queries in the incomplete first-order structures. Moreover, we propose a forcing-based definition of the internal interpretation of modal queries in such structures, and investigate some of the properties of this interpretation.
Equivalence Relations of Non-Deterministic Ianov-Schemes
Authors: De Frutos Escrig David , Indermark Klaus
Published: May 2021

We consider three different meanings of a non-deterministic Ianov-scheme with respect to infinite computations: trace-semantics, Plotkin-semantics, and Smyth-semantics. The corresponding equivalence relations are shown to be decidable.
A Nonmonotonic Logic of Belief
Authors: Moser Louise E.
Published: May 2021

A nonmonotonic logic of belief based on a combined monotonic logic of knowledge and belief is presented. Unlike previous nonmonotonic logics of belief, this logic contains an unless operator by means of which preference for beliefs and refutation of those beliefs can be expressed, thereby providing explicit representation of nonmonotonicity. A decision procedure based on Kripke structures for deciding validity of formulas in the logic is described and proved correct.
The Lambda Abstraction Strategy for Program Derivation
Authors: Pettorossi Alberto , Skowron Andrzej
Published: May 2021

In a previous paper of ours [Pettorossi-Skowron 87] we have introduced the higher order generalization strategy (also called lambda abstraction strategy) and we have indicated through some examples its use for the automatic derivation of programs. Here we study that strategy in more detail and we analyze its capabilities for obtaining highly efficient programs, considering also some cases in which other known strategies for program development do not work.
A Note on the Median Heuristic for Drawing Bipartite Graphs
Authors: Mäkinen Erkki
Published: May 2021

Eades and Wormald have shown that a bipartite graph drawn by the median heuristic has at most three times the number of edge crossing in the corresponding optimal drawing. In this paper we show that the bound of Eades and Wormald can be sharpened.
Some Structural Properties of Systolic Tree Automata
Authors: Fachini E. , Maggiolo Schettini A. , Resta G. , Sangiorgi D.
Published: May 2021

We prove that the classes of languages accepted by systolic automata over t-ary trees (t-STA) are always either equal or incomparable if one varies t. We introduce systolic tree automata with base (T(b)-STA), a subclass of STA with interesting properties of modularity, and we give a necessary and sufficient condition for the equivalence between a T(b)-STA and a t-STA, for a given base b. Finally, we show that the stability problem for T(b)-ST A is decidible.
Arithmetic Classification of Perfect Models of Stratified Programs
Authors: Apt Krzysztof R. , Blair Howard A.
Published: May 2021

We study here the recursion theoretic complexity of the perfect (Herbrand) models of stratified logic programs. We show that these models lie arbitrarily high in the arithmetic hierarchy. As a byproduct we obtain a similar characterization of the recursion theoretic complexity of the set of consequences in a number of formalisms for non-monotonic reasoning. We show that under some circumstances this complexity can be brought down to recursive enumerability.
Stratified, Weak Stratified, and Three-Valued Semantics1
Authors: Fitting Melvin , Ben-Jacob Marion
Published: May 2021

We investigate the relationship between three-valued Kripke/Kleene semantics and stratified semantics for stratifiable logic programs. We first show these are compatible, in the sense that if the three-valued semantics assigns a classical truth value, the stratified approach will assign the same value. Next, the familiar fixed point semantics for pure Horn clause programs gives both smallest and biggest fixed points fundamental roles. We show how to extend this idea to the family of stratifiable logic programs, producing a semantics we call weak stratified. Finally, we show weak stratified semantics coincides exactly with the three-valued approach on stratifiable programs, though the three-valued version is generally applicable, and does not require stratification assumptions.
A Compositional Semantics for Timed Petri Nets1
Authors: Maggiolo-Schettini Andrea , Winkowski Józef
Published: May 2021

Timed Petri nets and their behaviours are considered. A concept of a seminet is introduced. which generalizes the concept of a net, and suitable operations on seminets are defined, which allow constructing seminets from atoms corresponding to places and transitions. The behaviours of seminets are given in the form of so called configuration systems, a notion close to labelled event structures. Such behaviours can be combined with the aid of operations corresponding to those on seminets. In particular, the behaviour of a compound seminet can be obtained by combining the behaviours of components.
A Note on Rough Concepts Logic
Authors: Krynicki Michał
Published: May 2021

In papers [4,5] Pawlak introduced the notion of a rough set and approximation space. In [6] Pawlak formulated some concept of rough logic. The notion of the approximate truth was considered by many philosophers and logicians and in the last time by computer scientists. This was motivated by some research in artificial intelligence as for example expert systems, approximate reasoning methods and information system with imprecise information. The concept of rough logic introduced in [6] based on the notion of approximate truth determined by rough sets. Following these ideas Rasiowa and Skowron in [7] proposed the apropriate first order logic for concepts of rough definability. We denote this logic by LR. In [9] Szczerba proposed some logic with additional quantifier as rough concepts logic. We denote this logic by L(QR). The aim of this paper is a comparizing of these two logics with respect to their expressive power and giving some propositions of some modificated versions of rough concepts logics. We use more or less standard notation. By [a]R we denote the equivalence class of the element a with respect to the equivalence relation R. We write L ⩽ L ′ if expressive power of the logic L is weaker then t.he expressive power of the logic L ′ (i.e. each class of models definable by a sentence from L is also definable by a sentence from L ′ ). If L ⩽ L ′ and L ′ ⩽ L then we say that L and L ′ are equivalent and denote this by L ≡ L ′ . If L ⩽ L ′ but L ≢ L ′ then we write L < L ′ .
The Rough Sets Theory and Evidence Theory
Authors: Skowron Andrzej
Published: May 2021

The aim of the paper is to show some connections between the rough sets theory and the Dempser-Shafer approach. We prove that for every Pawlak’s approximation space there exists a Dempster-Shafer space with the qualities of the lower and upper approximations of sets in the approximation space equal to the credibility and plausibility of sets in the Dempster-Shafer space, respectively. Analogous connections hold between approximation spaces generated by the decision tables and Dempster-Shafer spaces, namely for every decision table space there exists a Dempster-Shafer space such that the qualities of the lower and upper approximations (with respect to the condition attributes) of sets definable in the decision table by condition and decision attributes coincide with the credibility and plausibility of sets in the Dempster-Shafer space, respectively. A combination rule in approximation spaces analogous to the combination rule used in the Dempster approach is derived.
Communicating Processes and Entropic Algebras
Authors: Romanowska Anna B. , Smith Jonathan D.H.
Published: May 2021

A significant contribution to the analysis of certain aspects of the communicating processes model was made by D. Benson’s proposal to view incompletely specified nondeterministic processes as modules over certain semirings, and dually as comodules over corresponding coalgebras. The effectiveness of the proposal in treating the synthesis of such processes under mutual communication depended on the good behaviour of these algebraic systems with respect to tensor products. The aim of the paper is to draw attension to the algebraic theory underlying Benson’s proposal, the theory of entropic algebras. Working with entropic algebras guarantees that tensor products are sufficiently well-behaved to make Benson’s theory work.
Algebraic Foundations of Logic Programming, I: The Distributive Lattice of Logic Programs
Authors: Hirani Anil , Subrahmanian V.S.
Published: May 2021

Given a logic program P, the operator TP associated with P is closely related to the intended meaning of P. Given a first order language L that is generated by finitely many non-logical symbols, our aim is to study the algebraic properties of the set {TP|P is a general logic program in language L} with certain operators on it. For the operators defined in this paper the resulting algebraic structure is a bounded distributive lattice. Our study extends (to the case of general logic programs), the work of Mancarella and Pedreschi who initiated a study of the algebraic properties of the space of pure logic programs. We study the algebraic properties of this set and identify the ideals and zero divisors. In addition, we prove that our algebra satisfies various non-extensibility conditions.
Infinitary Behaviours and Infinitary Observations
Authors: Darondeau Philippe , Gamatie Boubakar
Published: May 2021

We present a denotational model for CCS, accounting for finite as well as infinite behaviours. The meanings of programs are combinations of ready sets and infinitary languages. The model is shown fully abstract w.r.t. the equivalence u ∼ v if L(u,t)=L(v,t) for any testing program t, where L(p,q) is the set of totally ordered traces of communications between programs p and q set in parallel.
Minimization of Resolution Proof Systems
Authors: Stachniak Zbigniew
Published: May 2021

In this paper we show that minimal resolution counterparts of strongly finite logics can be effectively constructed. Moreover, we show that the class of resolution counterparts of structural propositional logics coincides with the class of resolution counterparts of strongly finite logics.
Unified Theory of Database Serializability12
Authors: Vidyasankar K.
Published: May 2021

A database system is a collection of data items, read or written by transactions in a possibly interleaved fashion. An interleaved execution is assumed to be correct if the sequence of the steps of the transactions, called history, is serializable, that is, the effect of the execution is equivalent to that of some serial execution of the same transactions. In this paper we give a new characterization of serializability that brings out the inherent problem of serialization explicitly. We then give a graph-theoretic analogue of serializable histories. We define a new class of graphs, called serializable graphs, whose properties are such that (i) a serializable graph can be associated with each serializable history, and this can be done for various notions of serializability of histories and for serializability under various sets of constraints, and (ii) a serializable history, in fact a serial one, can be associated with each serializable graph. We use serializable graphs to characterize, in an intuitive manner, serializable histories involving general multi-step transactions, where the same data item can be accessed by several read and write steps of a transaction in an arbitrary manner, and those involving nested transactions. We also define a new notion of serializability for nested transactions. This enables relating several acceptable concurrent executions of transactions, that are not serializable with the traditional transaction concept, to sequential behaviour. Serializability under this notion is also characterized. The main graph-theoretic properties used in these characterizations are a directed cutset matching property and graph contraction.
Axiom System Induced by CTL* Logic
Authors: Koutny Maciej
Published: May 2021

We discuss some of the problems concerning bisimulation relations over behaviour expressions representing non-sequential systems. The kind of bisimulation we investigate is derived from the notion of bisimulation relation between two Kripke structures, which provides a full characterisation of semantical equivalence of such structures w.r.t. the CTL* branching time temporal logic without the next-time operator. This new bisimulation on behaviour expressions, called CTL*-bisimulation, induces a congruence on recursion-free behaviour expressions, and in this paper we derive a sound and complete axiom system for this congruence.
Temporal Logic and Recursion
Authors: Kröger Fred , Merz Stephan
Published: May 2021

We propose a temporal logic based on structures divided into several layers of linear “time scales” and give a sound and complete derivation system. The logic is applied to the formulation and verification of assertions about sequential recursive programs.
On Processing of Fuzzy Production Systems
Authors: Stoeva Stefka P.
Published: May 2021

Knowledge bases in the form of fuzzy production systems with weighting coefficients, i.e. sets of weighted fuzzy rules, are studied. A software implementation of a rule-firing algorithm. based on Zadeh’s generalized modus ponens. is presented. The time complexity of the algorithm proposed is determined. Different types of parallelism in processing of fuzzy production systems are explored.
Embedding a Default System into Nonmonotonic Logics
Authors: Kaminski Michael
Published: May 2021

An embedding of minimal sets for default theories into nonmonotonic and nonmonotonic ground logics based on S4 and S5 is presented.
Jungle Evaluation
Authors: Habel Annegret , Kreowski Hans-Jörg , Plump Detlef
Published: May 2021

Jungle evaluation is proposed as a new graph rewriting approach to the evaluation of functional expressions and, in particular, of algebraically specified operations. Jungles – being intuitively forests of coalesced trees with shared substructures – are certain acyclic hypergraphs (or equivalently, bipartite graphs) the nodes and edges of which are labeled with the sorts and operation symbols of a signature. Jungles are manipulated and evaluated by the application of jungle rewrite rules, which generalize equations or, more exactly, term rewrite rules. Indeed, jungle evaluation turns out to be a compromise between term rewriting and graph rewriting displaying some favorable properties: the inefficiency of term rewriting is partly avoided while the possibility of structural induction is maintained, and a good part of the existing graph grammar theory is applicable so that there is some hope that the rich theory of term rewriting is not lost forever without a substitute.
On the Power of Two-Dimensional Synchronized Alternating Finite Automata1
Authors: Hromkovič Juraj , Inoue Katsushi , Ito Akira , Takanami Itsuo
Published: May 2021

It is well known that four-way two-dimensional alternating finite automata are more powerful than three-way two-dimensional alternating finite automata, which are more powerful than two-way two-dimensional alternating finite automata. This paper shows that four-way, three-way, and two-way two-dimensional “synchronized” alternating finite automata all have the same power as rectangular array bounded automata.
Towards an Approximation Theory of Discrete Problems. Part I
Authors: Skowron Andrzej , Stepaniuk Jaroslaw
Published: May 2021

The purpose of this paper is to make the first step towards an approximation theory of discrete problems in which one can express and prove properties of approximating algorithms as well as carry out an approximate reasoning. We introduce an approximation propositional dynamic logic (APDL) with approximations of programs and formulas. We discuss the expressibility of APDL. The main theorem is the completeness theorem for a fragment of APDL. We consider also the approximation problem of properties expressible in APDL by a distinguished set of so called simple approximate formulas and programs, generated only from approximations of atomic properties and approximations of atomic programs. The solution of the uniform approximation problem is presented and a result about an appoximation of decision algorithms is given.
Timed Possibilistic Logic
Authors: Dubois Didier , Lang Jérôme , Prade Henri
Published: May 2021

This paper is an attempt to cast both uncertainty and time in a logical framework. It generalizes possibilistic logic, previously developed by the authors, where each classical formula is associated with a weight which obeys the laws of possibility theory. In the possibilistic temporal logic we present here, each formula is associated with a time set (a fuzzy set in the more general case) which represents the set of instants where the formula is certainly true (more or less certainly true in the general case). When a particular instant is fixed we recover possibilistic logic. Timed possibilistic logic generalizes possibilistic logic also in the sense that we substitute the lattice structure of the set of the (fuzzy) subsets of the temporal scale to the lattice structure underlying the certainty weights in possibilistic logic. Thus many results from possibilistic logic can be straightforwardly generalized to timed possibilistic logic. Illustrative examples are given.
Monotonic and Non-Monotonic Logics of Knowledge1
Authors: Parikh Rohit
Published: May 2021

We study monotonic and non-monotonic Logics of Knowledge, giving decision procedures and completeness results. In particular we develop a model theory for a non-monotonic Logic of Knowledge and show that it corresponds exactly to normal applications of a non-monotonic rule of inference due to McCarthy.
A Semantic Approach to Fairness
Authors: Rutten J.J.M.M. , Zucker J.I.
Published: May 2021

In the semantic framework of metric process theory, we undertake a general investigation of fairness of processes from two points of view: (1) intrinsic fairness of processes, and (2) fair operations on processes. Regarding (1), we shall define a “fairification” operation on processes called Fair such that for every (generally unfair) process p the process Fair(p) is fair, and contains precisely those paths of p that are fair. Its definition uses systematic alternation of random choices. The second part of this paper treats the notion of fair operations on processes: suppose given an operator on processes (like merge, or infinite iteration), we want to define a fair version of it. For the operation of infinite iteration we define a fair version, again by a “fair scheduling” technique.
On Consistency and Completeness of Autoepistemic Theories
Authors: Gelfond Michael , Przymusinska Halina
Published: May 2021

In this paper we expand the results on existence and uniqueness of stable autoepistemic expansions for finite stratified autoepistemic theories to the infinite case. We also introduce a notion of the closed world completion of autoepistemic theory T, which can be viewed as an autoepistemic version of Closed World Assumption. We describe a class of autoepistemic theories called strongly stratified and prove that closed world completions of such theories have consistent stable autoepistemic expansions.
Towards a Categorical Semantics of Type Classes
Authors: Hilken Barney P. , Rydeheard David E.
Published: May 2021

This is an exercise in the description of programming languages as indexed categories. Type classes have been introduced into functional programming languages to provide a uniform framework for ‘overloading’. We establish a correspondence between type classes and comprehension schemata in categories. A coherence result allows us to describe subclasses and implicit conversions between types.
Operational and Denotational Semantics with Explicit Concurrency
Authors: Broy Manfred
Published: May 2021

The semantics of a simple language for describing tightly coupled “synchronous” systems is defined in terms of action structures representing histories of computations with explicit concurrency. An operational semantics is defined by term rewriting rules labelled by action structures. A consistent denotational semantics in terms of action structures is defined based on the concept of observable behaviour and on fixpoint theory. A fully abstract denotational semantics is given. In particular, the issue of interleaving semantics versus semantics including explicit concurrency is discussed.
Further Remarks on Reduced Languages
Authors: Paun Gheorghe , Szijarto Miklos , Vicolov Sorina
Published: May 2021

Union, homomorphic and inverse homomorphic representations of languages are obtained, starting from reduced languages introduced in earlier formal language approaches to parallel program schemes. The reduced-ness decidability is also investigated (it is decidable for regular and undecidable for linear languages).
Learning Programs with an Easy to Calculate Set of Errors1
Authors: Gasarch William I. , Sitaraman Ramesh K. , Smith Carl H. , Velauthapillai Mahendran
Published: May 2021

Within the study of inductive inference a recurring theme has been to investigate the learning of programs that are not exactly correct. Previous work attempted to quantify the difference between the function to be learned and the one computed by the result of a learning process. In this paper we study a qualitative measure of approximate correctness of the result of attempting to learn a program for a given function. What we require is that the set of errors be somehow easy to describe.
Epistemic Entrenchment in Autoepistemic Logic
Authors: Boutilier Craig
Published: May 2021

A drawback of existing epistemic logics is their inability to deal with entrenchment of beliefs. All beliefs have equal status; none can be held more firmly than others. We present a bimodal logic that generalizes Levesque’s reconstruction of autoepistemic logic. In our system standard epistemic concepts can be represented, including the notion of only knowing, but elements of a belief set may be more or less entrenched. This has important implications for the distinction between epistemic defaults and subjunctive (and normative) defaults, both of which are representable in our system.