bluuebunny/crossref_metadata_2025 huggingface dataset:
Controlled H Systems and Chomsky Hierarchy
Authors: Paun Gheorghe
Published: December 2019

This paper is an up-to-dated survey of results about the power of controlled extended H systems of various types. Such systems are finite generative devices based on the splicing operation, which, in turn, is a model of the DNA recombination. When no control is imposed on the splicing operation, we get a characterization of regular languages. When a control is considered, we obtain characterizations of recursively enumerable languages. We briefly discuss here H systems with control mechanisms similar to those in regulated rewriting area in formal language theory. We do not present proofs, but only definitions, results, and bibliographical information. Looking for characterizations of families in Chomsky hierarchy other than those of regular and of recursively enumerable languages, we closely investigate the H systems with permitting context conditions. We disprove a conjecture of Chakaravarthy and Krithivasan: such systems of radius one and using only one-sided context conditions can generate all context-free languages (the conjecture was that a characterization of linear languages is obtained). Some open problems are also mentioned.
A Representation of Processes of Petri Nets by Matrices
Authors: Winkowski Józef
Published: December 2019

A correspondence between processes of Petri nets and partitioned matrices over freely generated semirings is described. This correspondence implies a correspondence between operations of composing processes sequentially and in parallel and operations of multiplying and juxtaposing the respective partitioned matrices. It results in a characterization of partitioned matrices corresponding to processes of a given net and, consequently, allows one to represent processes by their matrices.
On Generalized Ajdukiewicz and Lambek Calculi and Grammars
Authors: Kandulski Maciej
Published: December 2019

We show that derivation trees in the generalized Lambek calculus can be transformed to a normal form. This fact is employed in the proof of the inclusion of the class of phrase languages generated by categorial grammars based on the generalized Lambek calculus in the class of phrase languages generated by categorial grammars based on the generalized Ajdukiewicz calculus.
Double-pushout hypergraph rewriting using total conformisms
Authors: Llabrés Mercè , Rosselló Francesc
Published: December 2019

The algebraic transformation of hypergraphs, under the so-called double-pushout (DPO) approach, was invented more than two decades ago, and thoroughly developed since then. We introduce in this paper a new approach to DPO algebraic transformation of hypergraphs and, more in general, of unary partial algebras, which generalizes the aforementioned “classical” DPO approach to hypergraph transformation. While the classical approach was based on the (usual) homomorphisms of hypergraphs, our new approach is based on the total conformisms, a type of morphisms of hypergraphs imported from the theory of partial algebras, which can be described, roughly speaking, as those mappings between hypergraphs that “reflect” the structure of the target object. In this paper we give both an algebraic and an operational characterization of this new DPO transformation, first for unary partial algebras and then, as a particular case, for hypergraphs. We also study its abstract properties related to parallelism and concurrency through the determination of the HLR conditions it satisfies with respect to several natural classes of morphisms.
Formal Verification and Diagnosis of Combinational Circuit Designs with Propositional Logic
Authors: Lee Shie-Jue , Lin Wei-Jer
Published: December 2019

Zero-defect is extremely important for VLSI designs. Formal techniques for verifying the correctness of logic designs overcome the limits of test case simulation. Many formal systems have been proposed for verification purpose. However, verification of VLSI designs is not enough. It would be equally or more important to correct wrong designs. Little attention has been paid on diagnosis of logic designs. We propose a formal system, based on a propositional logic theorem prover, to verify a combinational logic design and to fix the design if it is incorrect. By referring to the models obtained for an incorrect design and applying some heuristics, the system can locate errors and correct the design in an intelligent way.
Natural Computation for Natural Language
Authors: Martín-Vide Carlos
Published: December 2019

Computation not only takes place in provoked contexts of scientific experimentation, but in natural circumstances too. We are going to approach computation in natural contexts. How the nature computes? Turing machines and Chomsky grammars are rewriting systems, and the same is true for Post, Thue, Markov, Lindenmayer and other classes of axiomatic systems. If, among the whole set of natural objects, we focus natural language description, we must say that major trends in contemporary linguistics look at syntax as a rewriting process. Is rewriting unavoidable in this case, does our mind work by rewriting, does the nature compute in this way? We shall attempt to defend that the answer could be negative. The arguments will come from computability theory as well as from linguistics. First we'll formally explain the former ones, then informally the latter ones. With regard to computability theory arguments, we will see that, using the operation of adjoining, a large generative capacity is obtained. This is the case with contextual grammars. It has recently been proved that each recursively enumerable language is the quotient by a regular language of a language generated by a contextual grammar of a particular form. Thus, adjoining (paste) and quotient (cut) lead to computational universality. Recursively enumerable languages can also be characterized as the quotient by a regular language of a language generated by an insertion grammar. The same result is obtained if we take the splicing operation, a formal model of the DNA recombination. This is again a cut-and-paste operation. On the basis of the proof of this result, several further characterizations of recursively enumerable languages have been obtained. Computability theory, then, could be reconstructed without rewriting (and non-terminal symbols) and without any loss in power. Our first aim will be to show some formal aspects of such reconstruction. Later, we'll try to obtain some consequences for the future development of generative theory of natural language.
Partial Structural Synthesis of Programs
Authors: Matskin Mihhail , Komorowski Jan
Published: December 2019

The notion of partial deduction known from logic programming is defined in the framework of Structural Synthesis of Programs (SSP). Partial deduction for computability statements in SSP is defined. Completeness and correctness of partial deduction in the framework of SSP are proven. Several tactics and stopping criteria are suggested.
Bounds on Average Weighted Depth of Decision Trees
Authors: Moshkov Mikhail , Chikalov Igor
Published: December 2019

Upper and lower bounds on minimal average weighted depth and minimal average depth of decision trees over arbitrary information systems are considered. In proofs methods of test theory and rough set theory are used.
A Partial Order Representation of Processes of Transforming Graphs
Authors: Maggiolo-Schettini Andrea , Winkowski Józef
Published: December 2019

A model of processes of transforming graphs is proposed in which concurrency and branching can be represented. Operations on structures representing processes of transforming graphs are defined that allow one to construct such structures from simple components and to characterize sets of processes of transforming graphs, including sets of processes generated by graph grammars.
A Concurrent Functional Semantics for a Process Algebra Based on Action Systems
Authors: Montanari Ugo , Ristori Gioia
Published: December 2019

In [5, 8] a compositional, algebraic framework is provided in which shared memory systems can be specified and analyzed. The interferences in the use of the shared data are modelled, at the abstract level, by a conflict relation among the actions of the system. The semantic model of the process algebra language is defined in such a way that conflicting actions cannot be executed in parallel, whilst independent actions can. We show in the paper that conflict-based semantics do not allow for exploiting all the parallelism among the activities of a system. Actually, there are functionally equivalent programs (i.e. programs that compute the same final states of the activities and data) which perform conflicting actions in different order. In these situations, conflict-based semantics are not satisfactory, since they put useless sequential constraints on the executions. In this paper we define a concurrent semantics for the process algebra language in [5] which is in agreement with functional equivalence. We propose a model for the language which embeds both concurrent and functional aspects of programs, and takes into account two fundamental topics: the enhancement of the parallelism among the activities of the system, and the functional correctness of its computations. The formalism we use is that of Contextual Condition Event nets [12] (CC/E nets). By using CC/E nets we provide a faithful description of both the data and the activities of a shared memory system, in such a way that each process algebra term can be described by means of a set of net computations. The concurrent semantics of a term is then obtained by associating a structure called O-process [4] with each net computation. This semantics is in full agreement with functional equivalence, i.e. two process algebra terms compute the same final states of the activities and data if and only if they have the same concurrent semantics.
The Kernel of a Relational Morphism of Categories
Authors: Rey Jean-François
Published: December 2019

This paper introduces the notion of the kernel of a relational morphism of categories. This is the second step in the working out of a useful definition of the block product of two C-varieties which in turn is needed for the theory of decompositions of monoids by means of wreath or block products. In a previous work, the author defined the construction of the block product of two categories and the strong semidirect product functor. In this second part, we construct a left adjoint of the strong semidirect product functor which is the starting point of our construction of the kernel of a relational morphism. With these notions we define the block product of two C-varieties and prove a kernel theorem in the category settings which extends a work of J. Rhodes and B. Tilson.
The Topos of Labelled Trees: A Categorical Semantics for SCCS
Authors: Kasangian Stefano , Vigna Sebastiano
Published: December 2019

In this paper a we give a semantics for SCCS using the constructions of the topos of labelled trees. The semantics accounts for all aspects of the original formulation of SCCS, including unbounded non-determinism. Then, a partial solution to the problem of characterizing bisimulation in terms of a class of morphisms is proposed. We define a class of morphisms of the topos of trees, called conflict preserving, such that two trees T and U are bisimilar iff there is a pair of conflict preserving morphisms f : T → U and g : U → T such that fgf = f and gfg = g. It is the first characterization which does not require the existence of a third quotient object. The results can be easily extended to more general transition systems.
Decision Problems Concerning a Power Series Generalization of DTOL Systems
Authors: Honkala Juha
Published: December 2019

We study a power series generalization of DTOL systems with main interest on decidability questions.
On Relation of Image Compression and Image Association
Authors: Skarbek Władysław
Published: December 2019

Based on two image compression schemes (MIT and RNS), it is shown that it is possible to associate similar object images using their intermediate representation. Thus both methods can be applied to large image database for both goals: high quality image compression and reliable search for queries by image content. MIT scheme of Moghaddam and Pentland is specialized to face images. It moves image comparison task from high dimensional image space to low dimensional principal subspace spanned on eigenfaces. The closest point in the subspace is used for image association. RNS scheme of the author represents images (not limited to a certain scene type) by recurrent neural subnetworks which together with a competition layer create an associative memory. The single recurrent subnetwork Ni is designed for the i-th image and it implements a stochastic nonlinear operator Fi. It can be shown that under realistic assumptions Fi has a unique attractor which is located in the vicinity of the original image. When at the input a noisy, incomplete or distorted image is presented, the associative recall is implemented in two stages. Firstly, a competition layer finds the most invariant subnetwork. Next, the selected recurrent subnetwork reconstructs in few iterations the original image.
Lambda Abstraction Algebras: Coordinatizing Models of Lambda Calculus
Authors: Pigozzi Don , Salibra Antonino
Published: December 2019

Lambda abstraction algebras are designed to algebraize the untyped lambda calculus in the same way cylindric and polyadic algebras algebraize the first-order logic; they are intended as an alternative to combinatory algebras in this regard. Like combinatory algebras they can be defined by true identities and thus form a variety in the sense of universal algebra. One feature of lambda abstraction algebras that sets them apart from combinatory algebras is the way variables in the lambda calculus are abtracted; this provides each lambda abstraction algebra with an implicit coordinate system. Another peculiar feature is the algebraic reformulation of (β)-conversion as the definition of abstract substitution. Functional lambda abstraction algebras arise as the “coordinatizations” of environment models or lambda models, the natural combinatory models of the lambda calculus. As in the case of cylindric and polyadic algebras, questions of the functional representation of various subclasses of lambda abstraction algebras are an important part of the theory. The main result of the paper is a stronger version of the functional representation theorem for locally finite lambda abstraction algebras, the algebraic analogue of the completeness theorem of lambda calculus. This result is used to study the connection between the combinatory models of the lambda calculus and lambda abstraction algebras. Two significant results of this kind are the existence of a strong categorical equivalence between lambda algebras and locally finite lambda abstraction algebras, and between lambda models and rich, locally finite lambda abstraction algebras.
Credibility of Information for Modelling Belief State and Its Change
Authors: Gomolińska Anna
Published: December 2019

Credibility of information is investigated for the purpose of modelling belief state and its change.
Formalising Abilities and Opportunities of Agents
Authors: van Linder B. , van der Hoek W. , Meyer J.-J. Ch.
Published: December 2019

We present a formal system to reason about and specify the behavior of multiple intelligent artificial agents. Essentially, each agent can perform certain actions, and it may possess a variety of information in order to reason about its and other agent's actions. Thus, our KARO-framework tries to deal formally with the notion of Knowledge, possessed by the agents, and their possible execution of actions. In particular, each agent may reason about its —or, alternatively, other's— Abilities to perform certain actions, the possible Results of such an execution and the availability of the Opportunities to take a particular action. Formally, we combine dynamic and epistemic logic into one modal system, and add the notion of ability to it. We demonstrate that there are several options to define the ability to perform a sequentially composed action, and we outline several properties under two alternative choices. Also, the agents' views on the correctness and feasibility of their plans are highlighted. Finally, the complications in the completeness proof for both systems indicate that the presence of abilities in the logic makes the use of infinite proof rules useful, if not inevitable.
Pattern Extraction from Data
Authors: Nguyen Sinh Hoa , Nguyen Hung Son
Published: December 2019

Searching for patterns is one of the main goals in data mining. Patterns have important applications in many KDD domains like rule extraction or classification. In this paper we present some methods of rule extraction by generalizing the existing approaches for the pattern problem. These methods, called partition of attribute values or grouping of attribute values, can be applied to decision tables with symbolic value attributes. If data tables contain symbolic and numeric attributes, some of the proposed methods can be used jointly with discretization methods. Moreover, these methods are applicable for incomplete data. The optimization problems for grouping of attribute values are either NP-complete or NP-hard. Hence we propose some heuristics returning approximate solutions for such problems.
The Ground Tree Transducer Game
Authors: Vágvölgyi Sandor
Published: December 2019

We introduce the ground tree transducer game (gtt game) played by Alpha and Beta. We deduce from the possibility of embedding gtt games into abstract games that for any gtt game there is either a winning Alpha-strategy or a winning Beta-strategy. We present several examples for the game, and show that any abstract game can be simulated by some gtt game 𝒢, a set S1 of Alpha-strategies for 𝒢, and a set S2 of Beta-strategies for 𝒢. Among several decidability and undecidability results, we show the following. It is decidable, given gtt games 𝒢1 and 𝒢2, whether 𝒢1 and 𝒢2 are equivalent. There is no algorithm to determine, given a gtt game 𝒢 and an Alpha-strategy π, whether π is a winning Alpha-strategy. There is no algorithm to determine, given a recursive set S of gtt games, whether or not there exists a game 𝒢 ∈,; S such that Alpha has a winning strategy for 𝒢.
General Domain Circumscription and its Effective Reductions
Authors: Doherty Patrick , Łukaszewicz Witold , Szałas Andrzej
Published: December 2019

We first define general domain circumscription (GDC) and provide it with a semantics. GDC subsumes existing domain circumscription proposals in that it allows varying of arbitrary predicates, functions, or constants, to maximize the minimization of the domain of a theory. We then show that for the class of semi-universal theories without function symbols, that the domain circumscription of such theories can be constructively reduced to logically equivalent first-order theories by using an extension of the DLS algorithm, previously proposed by the authors for reducing second-order formulas. We also show that for a certain class of domain circumscribed theories, that any arbitrary second-order circumscription policy applied to these theories is guaranteed to be reducible to a logically equivalent first-order theory. In the case of semi-universal theories with functions and arbitrary theories which are not separated, we provide additional results, which although not guaranteed to provide reductions in all cases, do provide reductions in some cases. These results are based on the use of fixpoint reductions.
On the Size of Stack and Synchronization Alphabets of Tree Automata
Authors: Rahonis George , Salomaa Kai
Published: December 2019

We consider classes of forests defined by synchronized and pushdown tree automata having a fixed size of, respectively, synchronization or pushdown alphabet. We show that such families have nice properties, for instance, they form either a sheaf or a strict alphabetic cone of forests. Furthermore, for the (deterministic and nondeterministic) synchronized tree automata and the real-time pushdown tree automata we obtain a strict infinite forest hierarchy with respect to the alphabet size.
Remarks on the Relationship Between Cooperating Distributed Grammar Systems and Lindenmayer Systems
Authors: Amin Mohamed
Published: December 2019

In [2] it is shown that the family of languages generated by cooperating distributed (CD) grammar systems with context-free components in the derivation modes = k, ≥ k, for k ≥ 2, and the family of E0L languages are incomparable. Because one of the languages used in the proof of the incomparability does not work, we fill here the gap, using another language. We also give an effective procedure for constructing an ET0L system from a given context-free cooperating/distributed (CD) grammar system working in the maximum mode of cooperation.
A Uniform Axiomatic View of Lists, Multisets, and Sets, and the Relevant Unification Algorithms
Authors: Dovier Agostino , Policriti Alberto , Rossi Gianfranco
Published: December 2019

The first-order theories of lists, multisets, compact lists (i.e., lists where the number of contiguous occurrences of each element is immaterial), and sets are introduced via axioms. Such axiomatizations are shown to be very well-suited for the integration with free functor symbols governed by the classical Clark's axioms in the context of (Constraint) Logic Programming. Adaptations of the extensionality principle to the various theories taken into account is then exploited in the design of unification algorithms for the considered data structures. All the theories presented can be combined providing frameworks to deal with several of the proposed data structures simultaneously. The unification algorithms proposed can be combined (merged) as well, to produce engines for such combination theories.
Optimizations of Rough Set Model
Authors: Stepaniuk Jaroslaw
Published: December 2019

Rough set methodology is based on concept (set) approximations constructed from available background knowledge represented in information systems [14]. In many applications only partial knowledge about approximated concepts is given. Hence quite often first a parametrized family of concept approximations is built and next, by parameters tuning the best, in a sense, approximation is chosen (see e.g. the variable precision rough set model [40]). In this paper we follow this approach in generalized approximation spaces. We discuss rough set model based on approximation spaces with uncertainty functions and rough inclusions. Elements of approximation space are parametrized, moreover for the proper application of such model to a particular data set it is necessary to make optimization of the parameters. We discuss not only basic properties of the mentioned model, but strategies of parameters optimization as well. We also present different notions of rough relations. Optimization of different parameters can be based on the degree of inclusion of relations defined by condition and decision attributes. Some illustration of presented methods on real life medical data set is also included.
On Entropy and Optimal Coding Cost for Stochastic Language
Authors: Zhiltsova Larissa
Published: December 2019

We investigate questions, relating to optimal binary coding of a language, for which a probability distribution is given on its words (for a stochastic language). As optimal we understand the coding, which gives minimum of mathematical expectation of a length of the coded word, or minimum of the coding cost. For any stochastic language with a finite value of the entropy we establish lower and upper bounds of the optimal coding cost, dependent only on the entropy, and we prove their unimprovability. For any stochastic context-free language with unique derivation it is found necessary and sufficient condition of existence of finite values of the optimal coding cost and the entropy. Also an effective method of calculation of the entropy is found for the case when the considered condition holds.
Randomized PRAM Simulation
Authors: Czech Zbigniew J. , Mikanik Wojciech
Published: December 2019

The parallel random access machine (PRAM) is the most commonly used general-purpose machine model for describing parallel computations. Unfortunately the PRAM model is not physically realizable, since on large machines a parallel shared memory access can only be accomplished at the cost of a significant time delay. A number of PRAM simulation algorithms are known. The algorithms allow execution of PRAM programs on more realistic parallel machines. We study the randomized simulation of an exclusive read, exclusive write (EREW) PRAM on a module parallel computer (MPC). The simulation is based on utilizing universal hashing. The optimally efficient simulation involving parallel slackness is also investigated. The results of our experiments performed on the MPC built upon IMS T9000 transputers throw some light on the question whether using the PRAM model in parallel computations is practically viable given the present state of transputer technology.
Representing Hand-Shake Channel Communication in the Calculus of Cause-Effect Structures
Authors: Czaja Ludwik
Published: December 2019

It is shown how control aspects of the CSP-like communication mechanism may be represented as cause-effect structures, by using their calculus. A correctness proof of this transformation, i.e. its preserving of behaviour, has been given. A CSP-like parallel combinator for c-e structures is proposed, as well as its semantic counterpart. Compositionality property is proved.
Multi-Bracketed Contextual Rewriting Grammars
Authors: Kappes Martin
Published: December 2019

We study the generative capacity of multi-bracketed contextual rewriting grammars. This model is a generalization of multi-bracketed contextual grammars, which were studied in [Kap98a]. They possess an induced Dyck-structure to control the derivation process and to provide derivation trees. The generative capacity of this class is investigated and compared to Chomsky grammars and to tree adjoining grammars with local constraints. It will be shown that this class of grammars covers the basic natural language constructions such as duplication, multiple agreement and crossed-serial dependencies. Furthermore, two natural variants of the derivation relation, namely top-down and bottom-up derivation modes are examined.
Many-Valued Modal Non-Monotonic Reasoning: Sequential Stable Sets and Logics with Linear Truth Spaces
Authors: Koutras Costas D. , Koletsos George , Zachos Stathis
Published: December 2019

A family of many-valued modal logics which correspond to possible-worlds models with many-valued accessibility relations, has been recently proposed by M. Fitting [7, 8]. Non-monotonic extensions of these logics are introduced with a fixpoint construction à la McDermott & Doyle and employ sequential belief sets as epistemic states [9]. In this paper we take a logical investigation of many-valued modal non-monotonic reasoning in Fitting's formal framework. We examine the notion of MV-stable sets which emerges as a sequential many-valued analog of Stalnaker-Moore stable sets and prove that several attractive epistemic properties are essentially retained in the many-valued setting, esp. when focusing on a syntactically simple epistemic fragment of MV-stable sets. We show that MV-stable sets are always closed under S4 consequence and identify three sufficient conditions for capturing axioms of negative introspection. Also, the relation of MV-stable sets to many-valued analogs of classical S5 models and to many-valued extensions of universal models is discussed. Finally, we pay special attention to the subclass of logics built on linear Heyting algebras and show that inside this subclass, the situation is very similar - in many respects - to the machinery devised by W. Marek, G. Schwarz and M. Truszczyński. In particular, the normal fragments of the two important classical ranges of modal non-monotonic logics remain intact: many-valued autoepistemic logic is captured by any non-monotonic logic in K5 – KD45 and many-valued reflexive autoepistemic logic corresponds to KTw5 – Sw5.
A Comprehensive Setting for Matching and Unification over Iterative Terms
Authors: Intrigila B. , Inverardi P. , Venturini Zilli M.
Published: December 2019

Terms finitely representing infinite sequences of finite first-order terms have received attention by several authors. In this paper, we consider the class of recurrent terms proposed by H. Chen and J. Hsiang, and we extend it to allow infinite terms. This extension helps in clarifying the relationships between matching and unification over the class of terms we consider, that we call iterative terms. In fact, it holds that if a term s matches a term t by a substitution Γ, then the limit of iterations of the matching Γ, if it exists, is a most general unifier of s and t. A crucial feature of iterative terms is the notion of maximally-folded normal form that allows for a comprehensive treatment of both finite and infinite iterative terms. In this setting, infinite terms can be simply characterized as limits of sequences of finite terms. For finite terms we positively settle an open problem of H. Chen and J. Hsiang on the number of most general unifiers for a pair of terms.
Contributions to the Theory of Rough Sets
Authors: Marek V. Wiktor , Truszczyński Mirosław
Published: December 2019

We study properties of rough sets, that is, approximations to sets of records in a database or, more formally, to subsets of the universe of an information system. A rough set is a pair 〈L, U〉 such that L, U are definable in the information system and L ⊆ U. In the paper, we introduce a language, called the language of inclusion-exclusion, to describe incomplete specifications of (unknown) sets. We use rough sets in order to define a semantics for theories in the inclusion-exclusion language. We argue that our concept of a rough set is closely related to that introduced by Pawlak. We show that rough sets can be ordered by the knowledge ordering (denoted $\preceq$ kn)- We prove that Pawlak's rough sets are characterized as $\preceq$ kn-greatest approximations. We show that for any consistent (that is, satisfiable) theory T in the language of inclusion-exclusion there exists a $\preceq$ kn-greatest rough set approximating all sets X that satisfy T. For some classes of theories in the language of inclusion-exclusion, we provide algorithmic ways to find this best approximation. We also state a number of miscellaneous results and discuss some open problems.
A Relation Between Unambiguous Regular Expressions and Abstract Data Types
Authors: Preoteasa Viorel
Published: December 2019

Using a categorical model of abstract data types [2, 3, 13, 15], we show, following the Kozen's technique [10] and Tarjan's constructions for a deterministic automaton [16], that if two unambiguous regular expressions define the same regular language, then they represent two isomorphic abstract data types.
Computation of Extensions of Seminormal Default Theories
Authors: Su Kaile , Li Wei
Published: December 2019

In Reiter's default logic, the operator in the fixed-point definition of extension is not appropriate to compute extensions by its iterated applications. This paper presents a class of alternative operators, called compatible ones, such that, at least for normal default theories and so-called well-founded, ordered default theories, we can get extensions by iterated applications of them. In addition, we completely answer Etherington's conjectures about both his procedure for generating extensions and a modified version of it. In particular, we give an example of a finite, ordered default theory, for which the original procedure fails to converge, and show that the computation of the modified one is essentially the iteration of a compatible operator and converges for finite, ordered theories.
Full Abstractness of a Metric Semantics for Action Refinement
Authors: den Hartog J.I. , de Vink E.P. , de Bakker J.W.
Published: December 2019

For a process language with action refinement and synchronization both an operational and a denotational semantics are given. The operational semantics is based on an SOS-style transition system specification involving syntactical refinement sequences. The denotational semantics is an interleaving model which uses semantical refinement ‘environments'. It identifies those statements which are equal under all refinements. The denotational model is shown to be fully abstract with respect to the operational one. The underlying metric machinery is exploited to obtain this full abstractness result. Usually, action refinement is treated either in a model with some form of true concurrency, or, when an interleaving model is applied, by assuming that the refining statements are atomized. We argue that an interleaving model without such atomization is attractive as well.
Testing and Debugging Message Passing Programs in Synergy with their Specifications
Authors: Tsiatsoulis Z. , Cotronis J.Y.
Published: December 2019

We outline Ensemble, a design and implementation methodology for composing message passing (MP) applications from program components directed by scripts. We define specification components corresponding to program components and we compose them, directed by the same scripts, obtaining formal specifications of the composed applications. We use the Petri net formalism to express component and application specifications. Petri Net composition is modelled by appropriate coupling of inscriptions on interface input and output arcs to and from a unified environment place. We elaborate on testing and debugging of MP applications based on the synergy of tools for Petri-Net simulations with tools for monitoring program executions.
Formalisation of a Production System Modelling Language The operational semantics of χ Core
Authors: Bos V. , Kleijn J.J.T.
Published: December 2019

The formal language χ Core is derived from the systems engineering specification language χ. The language has its roots in Mechanical Engineering where it was designed to specify and analyse production systems. These production systems are described by concurrent communicating processes and can be analysed with the χ simulator. χ Core is a formalisation and simplification of the semantics of the χ language. Our motivation to design χ Core is the lack of a properly defined semantics of the χ specification language itself and the need for improved opportunities for the analysis of production systems. The operational semantics of χ Core is defined in a standard SOS-style. A bisimulation on χ Core processes is defined and shown to be a congruence. Based on this bisimulation, properties and time aspects of χ Core processes are discussed. The relation between χ and χ Core is explained by means of a translation scheme. Finally, an example specification of a production system is given and conclusions are drawn.
Similarity-based Unification
Authors: Formato Ferrante , Gerla Giangiacomo , Sessa Maria I.
Published: December 2019

Unification plays a central rule in Logic Programming. We ”soften” the unification process by admitting that two first order expressions can be ”similar” up to a certain degree and not necessarly identical. An extension of the classical unification theory is proposed accordingly. Indeed, in our approach, inspirated by the unification algorithm of Martelli-Montanari, the systems of equations go through a series of ”sound” transformations until a solvable form is found yielding a substitution that is proved to be a most general extended unifier for the given system of equations.
A Signal Extension for Petri Nets and its Use in Controller Design
Authors: Hanisch H.-M. , Lüder A.
Published: December 2019

Petri nets have a longstanding history in controller design and implementation, and it is often told that they have the dominating position in this field due to the close relationship between Petri nets and Graphcet or other sequential function diagrams. We want to show that there are some severe problems when Petri nets are used to describe both: the controller and the plant under control. The nature of these problems is the lack of a concept of input and output signals and, moreover, the lack of a formal concept to interconnect systems modeled by Petri nets via signals. Although this is often neglected, it turns out to be a key issue if a model of the closed-loop behavior must be established as a precondition for formal controller verification. We present a signal extension for Petri nets and means for interconnecting an arbitrary number of those extended Petri nets. We come up with the conclusion that the resulting models are suited for controller verification. Although the graphical appearance shows similarities to Petri nets, the resulting models are no longer Petri nets.
A Proof System for Dependencies for Information Relations
Authors: MacCaull Wendy
Published: December 2019

Using a relational approach, we investigate the implication problem for dependencies for information relations, focusing on functional dependencies, association rules and multivalued dependencies. We develop a Rasiowa/Sikorski-style relational calculus and show that the associated tableaux style of reasoning gives a decidable procedure for each of the three kinds of inference problems under consideration. This work has applications to classical database theory and to Rough Set Theory. The techniques may be generalized to the many other data dependencies which have formulations via binary relations and they can be applied to other information relations which arise in the study of incomplete information.
Formalizing Context in Intuitionistic Type Theory
Authors: Boldini Pascal
Published: December 2019

The article discusses formal aspects of the notion of context as needed in AI applications. We advocate the use of Martin-Löf's intuitionistic type theory to formalize and implement contexts. Through many examples belonging to the domains of computational semantics and knowledge based systems, we show that the built-in notion of context in intuitionistic type theory is a structure rich enough for representing most of the features that characterize contexts in an AI perspective. The fact that many recent theorem provers are built on the different theories of types suggests new perspectives in the development of AI applications.
A Method for Hierarchical Description of Images Using Multiscale Analysis
Authors: Inkielman Marcin
Published: December 2019

The aim of this paper is to present a novel method of image segmentation based on multiresolution analysis. The main idea consists of the extraction of image parts which are coherent and are enclosed by a coherent region classified to another type. Segmentation is processed in two steps. The first, consists of pixel classification into predefined types and the second is detection of the hierarchical structure of an image. The method is presented here on examples being biomedical images but it may be also applied to analyze other types of images.
Succinctness Gap between Monadic Logic and Duration Calculus
Authors: Rabinovich A.
Published: December 2019

In [8, 11] the expressive completeness of the Propositional fragment of Duration Calculus relative to monadic first-order logic of order was established. In this paper we show that there is at least an exponential blow-up in every meaning preserving translation from monadic logic to PDC. Hence, there exists an exponential gap between the succinctness of monadic logic and that of duration calculus.
The Nondeterministic Information Logic NIL is PSPACE-complete
Authors: Demri Stéphane
Published: December 2019

The nondeterministic information logic NIL has been introduced by Orłowska and Pawlak in 1984 as a logic for reasoning about total information systems with the similarity, the forward inclusion and the backward inclusion relations. In 1987, Vakarelov provides the first first-order characterization of structures derived from information systems and this has been done with the semantical structures of NIL. Since then, various extensions of NIL have been introduced and many issues for information logics about decidability and Hilbert-style proof systems have been solved. However, computational complexity issues have been seldom attacked in the literature mainly because the information logics are propositional polymodal logics with interdependent modal connectives. We show that NIL satisfiability is a PSPACE-complete problem. PSPACE-hardness is shown to be an easy consequence of PSPACE-hardness of the well-known modal logic S4. The main difficulty is to show that NIL satisfiability is in PSPACE. To do so we present an original construction that extends various previous works by Ladner (1977), Halpern and Moses (1992) and Spaan (1993).
Towards Automated Consistency Checking of Module Interface Specifications
Authors: Engel Marcin , Kret Artur , Mincer-Daszkiewicz Janina
Published: December 2019

The Trace Assertion Method (TAM) pioneered by Parnas is a formalism used to specify software module interfaces. The main purpose of the research described in this paper is to recognize the possibilities of linking the TAM editor with one of the existing theorem proving systems and to enable thereby the automated consistency checking of trace specifications. Possible approaches to embedding TAM in the Prototype Verification System (PVS) specification language are discussed and the chosen shallow definitional embedding is described in detail. Proof obligations for the consistency checking of trace specifications are obtained as type correctness conditions generated automatically by the PVS type checker. Some of these obligations can be proven automatically by PVS, other proofs need human guidance. Possible ways of increasing automation capabilities of the PVS theorem prover are recognized and presented. We share our experience in defining both specialized and general purpose proof strategies. This research may be viewed as a case study in applying the existing general purpose proof system to consistency checking of some application-specific formalism, which might be of interest for the software designer community.
Analysis of Timed Concurrent Models Based on Testing Equivalence
Authors: Andreeva Maria V. , Bozhenkova Elena N. , Virbitskaite Irina B.
Published: December 2019

The intention of the paper is to extend the testing methodology to a model of event structures with a dense time domain. Alternative characterizations of timed testing relations are provided. We also present algorithms for deciding timed testing for a subclass of the model under consideration. The key to our decision algorithms is that timed testing equivalences can be reduced to appropriate symbolic bisimulations.
Rational, Linear and Algebraic Process Languages and Iteration Lemmata
Authors: Czaja Ludwik , Kudlek Manfred
Published: December 2019

In this paper we define a certain class of process languages viewing processes as bipartite graphs with an associative operation (sequential composition) on them. They describe finite evolutions of Petri nets. When extended to sets, we get an ω-complete semiring such that rational, linear, and algebraic sets of such processes can be defined as least fixed points of systems of equations. With a norm of processes also iteration lemmata can be obtained. Finally, we also present a related structure of directed acyclic graphs.
A Multi-region Linear Logic Based Calculus for Dynamic Petri Net Structures
Authors: Farwer Berndt
Published: December 2019

Object based Petri nets are becoming increasingly popular in many fields of computer science. The possibility to model real-world objects as separate Petri nets supports the need for modular design of complex systems. So far object net approaches have been based on the presumption that the object nets' structure remains unchanged in all processes. This paper sheds some light on possible extensions of high-level Petri nets to incorporate the dynamical evolution of Petri net structures. The exposition is based on the Linear Logic encoding of Petri nets ([1], [12]) and coloured Petri nets ([4]). It provides a basic semantics for modifying net structures which can be employed in a framework of nets within nets, i.e. situations where Petri nets (so-called token nets) themselves are used as tokens in an underlying environment net.
Structural Analysis of Signal-Event Systems
Authors: Foremniak Adrianna , Starke Peter H.
Published: December 2019

Structural analysis explores the relation between local structural properties and the global functionality of nets. Here we consider Signal-Event systems under a generalized firing rule. The free-choice property and the deadlock-trap property are known from Petri net theory. We define them for Signal-Event nets and draw some consequences for liveness properties of Signal-Event systems.
Occurrence Net Logics
Authors: Haar Stefan
Published: December 2019

This paper investigates Occurrence (Petri) Nets on two levels: their structural theory and their interpretation in branching unfolding semantics of Petri Net systems. The key issue is the decomposition of occurrence nets into substructures given by the node relations associated with causal ordering, concurrency, and conflict. In addition to lines and cuts, which have long been studied in the context of causal nets ([1]), we introduce and study branches, trails, choices, and alternatives. All finite systems will be shown to satisfy certain density properties, i.e. non-empty intersections of substructures as above. On the semantic level, we introduce partial order logics to be interpreted on two different kind of frames, given by substructures of occurrence nets: on the frame of cuts, the CTL* type logics BFC and BLC, and the “non-branching” logic LLC, taylored to the frame given by the lattice of choices.
Timed Cooperating Automata
Authors: Lanotte Ruggero , Maggiolo-Schettini Andrea , Peron Adriano
Published: December 2019

We propose Timed Cooperating Automata (TCAs), an extension of the model Cooperating Automata of Harel and Drusinsky, and we investigate some basic properties. In particular we consider variants of TCAs based on the presence or absence of internal activity, urgency and reactivity, and we compare the expressiveness of these variants with that of the classical model of Timed Automata (TAs) and its extensions with periodic clock constraints and with silent moves. We consider also closure and decidability properties of TCAs and start a study on succinctness of their variants with respect to that of TAs.
ChariTime — Concepts of Analysis and Design of an Agent-Oriented System for Appointment Management
Authors: Münch Ines , Lindemann - v.Trzebiatowski Gabriela
Published: December 2019

Conceptual modeling is an important basis for developing general purpose systems for information and service management. In this paper, we present concepts for the analysis and design of a system of agents in which agents represent interests of individuals or groups. In particular, we develop a semantic model of agent domain knowledge by introducing analytical concepts for service scheduling which is the envisioned application of our prototypical system ChariTime.
TBase2 — a Web–Based Electronic Patient Record
Authors: Schröter Kay , Lindemann - v.Trzebiatowski Gabriela , Fritsche Lutz
Published: December 2019

Fast and easy access to all relevant data is of most importance in medical diagnostics and therapy. Electronic patient records can fulfil these requirements much better than common paper-based records. This article describes the TBase2 system, an example of such an electronic patient record. It was developed in close cooperation with the Department of Nephrology at the university hospital Charité in Berlin. Due to its flexibility TBase2 can easily be adapted to the demands of other departments. Beside supporting the daily care for patients, TBase2 also gathers detailed data of high validity ideally suited for medical research.