Two methods of the analysis of distorted (fuzzy) string patterns are presented. The methods are based on the use of GDPLL(k ) grammars generating a large subclass of context sensitive languages. The first one utilizes error-correcting approach: a minimum distance measure is used for error-correcting parsing. The second one utilizes stochastic approach: the decision about the production to be applied in a derivation step is given according to the probability measure.

The paper introduces the formal description of a computing multi-agent system (MAS), its architecture and dynamics (sections 2-4). The optimal scheduling problem for the MAS as well as a way of its verification are presented in terms of such a model (section 5). A brief report of test results published previously in [13,3,4,8] is contained in the section 6.

This work focuses on the dynamic Pickup and Delivery Problem with Time Windows (PDPTW). The transport requests should be performed using the available fleet of vehicles. The vehicles move between the nodes of a road network. The aim of this work is to propose a model which allows, during a transport plan creation, to take into account predictable events. Particularly, we consider the frequency of requests at any node in the road network and the construction of vehicle routes that will allow new requests to be inserted without any significant route modification. Therefore, we construct routes that pass near the nodes where transport requests are most frequently generated.

The contribution deals with a class of intelligent decentralized systems that meet the agent paradigm. Such systems are marked by the possibility of arising critical situations, interpreted here as the threat of loss (partial or complete) of the system functionality. The work is focused on designing an overall architecture of the (sub-)system dedicated to the discovery of crises and support of anti-crisis activities. The architecture is proposed as a reference one so as it is possible to adjust it to the specificity of any particular application. As an illustration the case of a transportation system is discussed.

Rough set theory is a paradigm for approximate reasoning based on a formal mathematical basis, viz., it assumes that concepts are divided into exact and non-exact (rough) ones by means of a topological structure induced by a representation of knowledge as a classification. A classification in its most simple form is an equivalence relation on a universe of objects; the classification induces a partition topology and concepts (subsets of the universe) that are clopen are exact whereas other concepts are rough. In consequence, rough sets are represented as pairs of exact sets of the form (interior, closure).

In the paper, we propose a set theory RZF that represents formally exact and rough sets as satisfying or not a certain dichotomy based on a new form of membership in a set; this membership acquires a mereological character as it is based on containment. As a result, we propose a new form of set theory suitable as a set theory for rough sets.

Logical models for reasoning in the framework of rough set theory were proposed and studied by many researchers, among them Orowska, Or owska and Pawlak, Rasiowa and Skowron, Vakarelov. We exploit here models of RZF as interpretation domains for rough mereological logics: intensional logics whose truth value assignment is based on rough inclusions - basic predicates of rough mereology, a paradigm for approximate reasoning introduced by Polkowski and Skowron.

An application for those logics is proposed in semantic interpretation of vague statements forming the domain of Calculus of Perceptions proposed by Zadeh.

This paper concerns problems of applying the approach based on rough sets and rule induction to a software engineering data analysis. More precisely, we focus our interest on a software cost estimation problem, which includes predicting the effort required to develop a software system basing on values of cost factors. The case study of analysing the COCOMO data set, containing descriptions of representative historical projects, allows us to discuss how this approach could be used to: identify the most discriminatory cost factors, extract meaningful rule representation of classification knowledge from data, construct accurate rule based classifiers.

Time is one of the most important considerations in designing practical systems. The notion of time plays a vital role in performance evaluation of real-time systems. A new class of timed approximate Petri nets (TAP-nets) is proposed in the paper. This net model combines high-level Petri nets with time and uncertain information. The approach presented in the paper for modelling of uncertainty, imprecision and vagueness is based on rough set theory and fuzzy Petri nets. The TAP-nets can be used for modelling and evaluating of approximate reasoning used to build expert systems, control systems, communication systems, etc. The main advantage of modelling practical systems using the TAP-nets is that the resulting models are simple, intuitive and allow the system analyst to evaluate the performance of such system models.

Petri nets are one of well established tools in both theoretical analysis and practical modelling of concurrent systems as well as approximate reasoning. However, practical usage of Petri nets is limited by the lack of computer tools which would allow to handle large and complex nets in a comfortable way. Three things are essential for modelling and analyzing by means of Petri nets - good editor, simulator and powerful analysis engine. Moreover, a program should have a graphical user interface providing an opportunity to work directly with the graphical representations of Petri nets and should be able to read and write data in formats of other popular simulators of Petri Nets.
This paper presents a set of integrated graphical Petri net tools called Petri Net system (PN-system, in short).

PN-system is a following version of PN-tools. This system can be used for constructing, editing and analyzing of different classes of Petri nets. PN-system is enhanced on fuzzy and adaptive fuzzy Petri nets' modules which allow to perform fuzzy reasoning automatically. It has got a graphical user interface. Moreover, PN-system can cooperate with the ROSECON system which is an original software tool for discovering concurrent models from data tables. PN-system is run on IBM PC platform under MS Windows operating system.

This paper deals with reconstruction of net models of concurrent systems described by information systems changing in time. Constructed net models have the form of coloured Petri nets. Resulting nets are constructed on the basis of decomposed information systems. In many practical cases, a description of modelled systems changes in time. New knowledge about structures and behaviours of systems appears. When new descriptions appear, the net models should be changed taking into consideration the new knowledge. An approach to reconstruction of net models is here presented. One of many possible cases is considered, i.e., when the new global state of the modelled system appears. The ability to compute reducts and components of a new information system, being a new description of a modelled system, in an efficient way is important for reconstruction. Therefore, some propositions and corollaries useful to compute reducts of a new information system on the basis of reducts of an old information system are given. These propositions and corollaries are the basis to formulate algorithms for computing new reducts and components. Moreover, a way to determine the cost of the reconstruction of a net model is given. The cost of the reconstruction is treated as the cost of adding new functional modules, communication lines or their modifications. The discussed approach to model reconstruction extends and refines that proposed by Z. Suraj in 1998. An example is given in this paper to illustrate the presented idea.

Pawlak had proposed the notion of rough truth in 1987 [16]. The article takes a fresh look at this ``soft'' truth, and presents a formal system L_R, that is shown to be sound and complete with respect to a semantics determined by this notion. L_R is based on the modal logic S5. Notable is the rough consequence relation defining L_R (a first version introduced in [9]), and rough consistency (also introduced in [9]), used to prove the completeness result. The former is defined in order to be able to derive roughly true propositions from roughly true premisses in an information system. The motivation for the latter stems from the observation that a proposition and its negation may well be roughly true together. A characterization of L_R-consequence shows that the paraconsistent discussive logic J of Ja\'skowski is equivalent to L_R. So, L_R, developed from a totally independent angle, viz. that of rough set theory, gives an alternative formulation to this well-studied logic. It is further observed that pre-rough logic [3] and 3-valued ukasiewicz logic are embeddable into L_R.

In a previous paper, we developed an algebraic theory about threads and multi-threading based on the assumption that a deterministic interleaving strategy determines how threads are interleaved. The theory includes interleaving operators for a number of plausible deterministic interleaving strategies. The interleaving of different threads constitutes a multi-thread. Several multi-threads may exist concurrently on a single host in a network, several host behaviors may exist concurrently in a single network on the internet, etc. In the current paper, we assume that the above-mentioned kind of interleaving is also present at these other levels. We extend the theory developed so far with features to cover the multi-level case. We use the resulting theory to develop a simplified formal representation schema of systems that consist of several multi-threaded programs on various hosts in different networks. We also investigate the connections of the resulting theory with the algebraic theory of processes known as ACP.

Disjunctive Logic Programming (DLP) is an advanced formalism for knowledge representation and reasoning. The language of DLP is very expressive and supports the representation of problems of high computational complexity (specifically, all problems in the complexity class \SigmaP2 = \NP^\NP). The DLP encoding of a large variety of problems is often very concise, simple, and elegant.

In this paper, we explain the computational process commonly performed by DLP systems, with a focus on search space pruning, which is crucial for the efficiency of such systems. We present two suitable operators for pruning (Fitting's and Well-founded), discuss their peculiarities and differences with respect to efficiency and effectiveness. We design an intelligent strategy for combining the two operators, exploiting the advantages of both. We implement our approach in DLV - the state-of-the-art DLP system - and perform some experiments. These experiments show interesting results, and evidence how the choice of the pruning operator affects the performance of DLP systems.

A novel method for the compression of the index table of vector quantization (VQ) is proposed in this paper. This method is designed based on the observation that neighboring image blocks are highly correlated. In other words, VQ-encoded neighboring image blocks tend to have similar indices if the codebook used in VQ is previously sorted by the principal component analysis technique. According to this characteristic, we find the same or similar indices around the current processing index to process it. In addition, the pre-statistics technique is employed to gather differences that appear most often in the index table. Simulation results indicate that the newly proposed scheme achieves significant reduction of bit rate without losing any image quality by the original VQ encoding.

A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node, without leaving any trace. We consider the task of locating a black hole in a (partially) synchronous network, assuming an upper bound on the time of any edge traversal by an agent. The minimum number of agents capable to identify a black hole is two. For a given graph and given starting node we are interested in the fastest possible black hole search by two agents, under the general scenario in which some subset of nodes is safe and the black hole can be located in one of the remaining nodes. We show that the problem of finding the fastest possible black hole search scheme by two agents is NP-hard, and we give a 9.3-approximation for it.

We study concurrent processes modelled as workflow Petri nets extended with resource constrains. Resources are durable units that can be neither created nor destroyed: they are claimed during the handling procedure and then released again. Typical kinds of resources are manpower, machinery, computer memory. We define structural criteria based on traps and siphons for the correctness of workflow nets with resource constraints. We also extend the soundness notion for workflow nets to the workflow nets with resource constraints; extra conditions concern the durability of resources. We prove some properties of sound resource-constrained workflow nets

In this paper we introduce the Weighted Suffix Tree, an efficient data structure for computing string regularities in weighted sequences of molecular data. Molecular Weighted Sequences can model important biological processes such as the DNA Assembly Process or the DNA-Protein Binding Process. Thus pattern matching or identification of repeated patterns, in biological weighted sequences is a very important procedure in the translation of gene expression and regulation. We present time and space efficient algorithms for constructing the weighted suffix tree and some applications of the proposed data structure to problems taken from the Molecular Biology area such as pattern matching, repeats discovery, discovery of the longest common subsequence of two weighted sequences and computation of covers.

This paper proposes a way to incorporate the idea of spiking neurons into the area of membrane computing, and to this aim we introduce a class of neural-like P systems which we call spiking neural P systems (in short, SN P systems). In these devices, the time (when the neurons fire and/or spike) plays an essential role. For instance, the result of a computation is the time between the moments when a specified neuron spikes. Seen as number computing devices, SN P systems are shown to be computationally complete (both in the generating and accepting modes, in the latter case also when restricting to deterministic systems). If the number of spikes present in the system is bounded, then the power of SN P systems falls drastically, and we get a characterization of semilinear sets. A series of research topics and open problems are formulated.

In this paper, we demonstrate how some simple graph counting operations on the ideal lattice representation of a partially ordered set (poset) P allow for the counting of the number of linear extensions of P, for the random generation of a linear extension of P, for the calculation of the rank probabilities for every x Î P, and, finally, for the calculation of the mutual rank probabilities Prob(x > y) for every (x,y) Î P².
We show that all linear extensions can be counted and a first random linear extension can be generated in O(|I(P)|·w(P) ) time, while every subsequent random linear extension can be obtained in O( |P|·w(P)) time, where |I(P)| denotes the number of ideals of the poset P and w(P) the width of the poset P. Furthermore, we show that all rank probability distributions can be computed in O( |I(P)|·w(P)) time, while the computation of all mutual rank probabilities requires O(|I(P)|·|P|·w(P)) time, to our knowledge the fastest exact algorithms currently known.
It is well known that each of the four problems described above resides in the class of #P-complete counting problems, the counterpart of the NP-complete class for decision problems. Since recent research has indicated that the ideal lattice representation of a poset can be obtained in constant amortized time, the stated time complexity expressions also cover the time needed to construct the ideal lattice representation itself, clearly favouring the use of our approach over the standard approach consisting of the exhaustive enumeration of all linear extensions.

This paper introduces a rough set approach to reinforcement learning by swarms of cooperating agents. The problem considered in this paper is how to guide reinforcement learning based on knowledge of acceptable behavior patterns. This is made possible by considering behavior patterns of swarms in the context of approximation spaces. Rough set theory introduced by Zdzisaw Pawlak in the early 1980s provides a ground for deriving pattern-based rewards within approximation spaces. Both conventional and approximation space-based forms of reinforcement comparison and the actor-critic method as well as two forms of the off-policy Monte Carlo learning control method are investigated in this article. The study of swarm behavior by collections of biologically-inspired bots is carried out in the context of an artificial ecosystem testbed. This ecosystem has an ethological basis that makes it possible to observe and explain the behavior of biological organisms that carries over into the study of reinforcement learning by interacting robotic devices. The results of ecosystem experiments with six forms of reinforcement learning are given. The contribution of this article is the presentation of several viable alternatives to conventional reinforcement learning methods defined in the context of approximation spaces.

Content-based image copy detection can be used as either an alternative approach or a complementary approach to watermarking. To detect copied versions of digital images, which are generated by various image processes, several schemes have been proposed. However, none of them can successfully detect tampering when those images are rotated 90 or 270 degrees from the original image. To solve this problem, we propose a new copy detection scheme based on Y component of image and block strategy. A test image is just converted to a YUV color model where only Y component is used to generate the image signatures. Then, the transformed image is divided into 8×8 blocks. Finally, the relationship between each block and its neighboring eight blocks are recorded by comparing these block's mean values. This image signature generated by our proposed scheme contains the comparative relationship between each block and its neighboring blocks. Our proposed scheme can detect modifications those are generated by 90 or 270 rotation of original one, which can not be detected by Kim's scheme. The optimal block numbers used for image partition have been explored and the efficiency of the proposed scheme is extensively tested with 20,000 test images.

We show that unlike the general case of the relationship between algorithmic probability and program-size for enumerating sets, in the case of the graphs of total functions these two quantities are closely related.

Without proper simplification techniques, database integrity checking can be prohibitively time consuming. Several methods have been developed for producing simplified incremental checks for each update but none until now of sufficient quality and generality for providing a true practical impact, and the present paper is an attempt to fill this gap. On the theoretical side, a general characterization is introduced of the problem of simplification of integrity constraints and a natural definition is given of what it means for a simplification procedure to be ideal. We prove that ideality of simplification is strictly related to query containment; in fact, an ideal simplification procedure can only exist in database languages for which query containment is decidable. However, simplifications that do not qualify as ideal may also be relevant for practical purposes. We present a concrete approach based on transformation operators that apply to integrity constraints written in a rich DATALOG-like language with negation. The resulting procedure produces, at design-time, simplified constraints for parametric transaction patterns, which can then be instantiated and checked for consistency at run-time. These tests take place before the execution of the update, so that only consistency-preserving updates are eventually given to the database. The extension to more expressive languages and the application of the framework to other contexts, such as data integration and concurrent database systems, are also discussed. Our experiments show that the simplifications obtained with our method may give rise to much better performance than with previous methods and that further improvements are achieved by checking consistency before executing the update.

An extended first-order predicate sequent calculus PLK with two kinds of negation is introduced as a basis of a new resolution calculus PRC (paraconsistent resolution calculus) for handling the property of paraconsistency. Herbrand theorem, completeness theorem (with respect to a classical-like semantics) and cut-elimination theorem are proved for PLK. The correspondence between PLK and PRC is shown by using a faithful embedding of PLK into the sequent calculus LK for classical logic.

A novel watermarking scheme that is capable of hiding authorization data in a gray-level image is proposed in this letter. The proposed scheme generates a key stream to be the key to connect the authorized image and its watermark. The key stream is extra data rather than data being embedded into the authorized image. Such arrangement can guarantee the integrity of the image. To reduce the complexity in computing the key stream for the authorized gray-level image, two techniques are employed in the proposed scheme. One is the concept of rehashing, and the other is the vector quantization. The benefits of the proposal are to provide a key stream to prove the gray-level's ownership, and to keep the authorized image in its original state without any modification.

The concept of hairpin structures in formal languages is motivated from the biocomputing and bioinformatics fields. Hairpin (-free) DNA structures have numerous applications to DNA computing and molecular genetics in general. A word is called hairpin-free if it cannot be written in the form xvyq(v)z, with certain additional conditions, for an involution q (a function q with the property that q² equals the identity function). A particular involution, the so-called Watson-Crick involution, can characterize binding of two DNA strands.

We study algebraic and decision properties, finiteness and descriptional complexity of hairpin (-free) languages. We show an existence of polynomial-time algorithms deciding hairpin-freeness of regular and context-free sets. Two related DNA secondary structures are considered, taking into the account imperfect bonds (bulges, mismatches) and multiple hairpins. Finally, effective methods for design of long hairpin-free DNA words are given.

Subtyping is a basic concept in object-oriented languages. It supports subsumption but, unfortunately, it does not support inheritance of binary methods, i.e., methods taking another argument of type Self - the same type as the object itself. For this reason, a relation, called matching, on recursive object types has been proposed. This relation does not support subsumption but it allows to inherit binary methods. Two different definitions of matching, called F-bounded and higher-order subtyping, have been proposed and discussed. It was shown that the higher-order interpretation has better theoretical properties, i.e., it leads to a reflexive and transitive matching relation. In this paper we concentrate on two problems in languages with self types and matching based on the higher-order interpretation. We show that the flexibility of self types may not allow the programmer to define certain classes and/or methods which are based on constant values. Furthermore, the higher-order interpretation, especially in the context of bounded quantification, is too restrictive. We argue that a language should be based on both versions of matching and a notion of a type This distinguished from the type Self.

Traditionally, due to efficiency considerations, when encrypting long messages using an asymmtric cryptosystem, one needs to use a symmetric cryptosystem in addition. To eliminate this requirement, Hwang, Chang, and Hwang introduced an asymmetric cryptosystem for encrypting long messages. However, they did not give any formal proof of the security of this cryptosystem. In this paper, we propose an improved asymmetric cryptosystem for encrypting long messages, which is both efficient and secure. In the aspect of efficiency, our cryptosystem is about twice as fast as the Hwang-Chang-Hwang cryptosystem. In the aspect of security, besides providing an informal analysis, we rigorously show that computing any part of the plaintext message encrypted using our cryptosystem is as hard as breaking the ElGamal cryptosystem, even if all other parts of the message are already known to the adversary.