111(1) 2011

1. Knowledge Technology. Preface i-ii
2. Double Approximation and Complete Lattices
   Taichi Haruna,  Yukio-Pegio Gunji 1-14
   We explore lattice theoretic aspects in rough set theory in terms of the duality between algebra and representation. Approximation spaces are dual to complete atomic Boolean algebras in the sense that there is an adjunction between corresponding suitable categories. This is an analogy with the adjunction between the category of topological spaces and the opposite of the category of frames in pointless topology. In this paper we consider a generalization of approximation spaces called double approximation systems. A double approximation system consists of a set and two equivalence relations on it. We construct an adjunction generalizing this concept for approximation spaces. To achieve this goal, we first introduce a natural generalization of complete atomic Boolean algebras called complete prime lattices. Then we select double approximation systems that can be dual to complete prime lattices and prove the adjunction.
3. Attribute Reduction in Formal Contexts: A Covering Rough Set Approach
   Tong-Jun Li,  Wei-Zhi Wu 15-32
   This paper proposes an approach to attribute reduction in formal contexts via a covering rough set theory. The notions of reducible attributes and irreducible attributes of a formal context are first introduced and their properties are examined. Judgment theorems for determining all attribute reducts in the formal context are then obtained. According to the attribute reducts, all attributes of the formal context are further classified into three types and the characteristic of each type is characterized by the properties of irreducible classes of the formal context. Finally, by using the discernibility attribute sets, a method of distinguishing the reducible attributes and the irreducible attributes in formal contexts is presented.
4. The Construction of Fuzzy Concept Lattices Based on (q,s)-Fuzzy Rough
   Approximation Operators
   Yanqing Yao,  Jusheng Mi,  Zhoujun Li,  Bin Xie 33-45
   Formal concept analysis and rough set analysis are two complementary approaches for analyzing data. This paper studies approaches to constructing fuzzy concept lattices based on generalized fuzzy rough approximation operators. For a residual implicator q satisfying q(a, b)=q(1-b, 1-a) and its dual s, a pair of (q,s)-fuzzy rough approximation operators is defined. We then propose three kinds of fuzzy operators, and examine some of their basic properties. Thus, three complete fuzzy concept lattices can be produced, for which the properties are analogous to those of the classical concept lattices.
5. Approximation Operators, Binary Relation and Basis Algebra in L-fuzzy Rough Sets
   Zhengjiang Wu,  Tianrui Li,  Keyun Qin,  Da Ruan 47-63
   Approximation operators play a vital role in rough set theory. Their three elements, namely, binary relation in the universe, basis algebra and properties, are fundamental in the study of approximation operators. In this paper, the interrelations among the three elements of approximation operators in L-fuzzy rough sets are discussed under the constructive approach, the axiomatic approach and the basis algebra choosing approach respectively. In the constructive approach, the properties of the approximation operators depend on the basis algebra and the binary relation. In the axiomatic approach, the induced binary relation is influenced by the axiom set and the basis algebra. In the basis algebra choosing approach, the basis algebra is constructed by properties of approximation operators and specific binary relations.
6. Kernelized Fuzzy Rough Sets Based Yawn Detection for Driver Fatigue Monitoring
   Yong Du,  Qinghua Hu,  Degang Chen,  Peijun Ma 65-79
   Driver fatigue detection based on computer vision is considered as one of the most hopeful applications of image recognition technology. The key issue is to extract and select useful features from the driver images. In this work, we use the properties of image sequences to describe states of drivers. In addition, we introduce a kernelized fuzzy rough sets based technique to evaluate quality of candidate features and select the useful subset. Fuzzy rough sets are widely discussed in dealing with uncertainty in data analysis. We construct an algorithm for feature evaluation and selection based on fuzzy rough set model. Two classification algorithms are introduced to validate the selected features. The experimental results show the effectiveness of the proposed techniques.
7. A Novel Multimodal Probability Model for Cluster Analysis
   Jian Yu,  Miin-Shen Yang,  Pengwei Hao 81-90
   Cluster analysis is a tool for data analysis. It is a method for finding clusters of a data set with most similarity in the same group and most dissimilarity between different groups. In general, there are two ways, mixture distributions and classification maximum likelihood method, to use probability models for cluster analysis. However, the corresponding probability distributions to most clustering algorithms such as fuzzy c-means, possibilistic c-means, mode-seeking methods, etc., have not yet been found. In this paper, we construct a multimodal probability distribution model and then present the relationships between many clustering algorithms and the proposed model via the maximum likelihood estimation. Moreover, we also give the theoretical properties of the proposed multimodal probability distribution.
8. Object-Oriented Inheritance Metrics in the Context of Cognitive Complexity
   Deepti Mishra,  Alok Mishra 91-117
   It is important to identify modules that are fault prone or exhibit evidence of high cognitive complexity as these modules require corrective actions such as increased source code inspection, refactoring or performing more exhaustive testing. This can lead to a better quality software system. It has been found that inheritance has an impact on the cognitive complexity of a software system. In this paper, two inheritance metrics based on cognitive complexity, one at class level CCI (Class Complexity due to Inheritance) and another at program level ACI (Average Complexity of a program due to Inheritance), have been proposed for object-oriented software systems. Additionally, one more metric MC (Method Complexity) has been proposed to calculate the complexity of a method. These proposed metrics are compared with some well known object-oriented inheritance metrics by calculating their values for three random C++ programs. It has been observed that CCI and ACI are better to represent cognitive complexity due to inheritance than other well known class level and program level inheritance metrics.

111(2) 2011

1. On the Generative Power of w-Grammars and w-Automata
   Zhe Chen 119-145
   An w-grammar is a formal grammar used to generate w-words (i.e. infinite length words), while an w-automaton is an automaton used to recognize w-words. This paper gives clean and uniform definitions for w-grammars and w-automata, provides a systematic study of the generative power of w-grammars with respect to w-automata, and presents a complete set of results for various types of w-grammars and acceptance modes. We use the tuple (s,r,p) to denote various acceptance modes, where s denotes that some designated elements should appear at least once or infinitely often, r denotes some binary relation between two sets, and p denotes normal or leftmost derivations. Technically, we propose (s,r,p)-accepting w-grammars, and systematically study their relative generative power with respect to (s,r)-accepting w-automata. We show how to construct some special forms of w-grammars, such as e-production-free w-grammars. We study the equivalence or inclusion relations between w-grammars and w-automata by establishing the translation techniques. In particular, we show that, for some acceptance modes, the generative power of w-CFG is strictly weaker than w-PDA, and the generative power of w-CSG is equal to w-TM (rather than linear-bounded w-automata-like devices). Furthermore, we raise some remaining open problems for two of the acceptance modes.
2. Infinite Traces and Symbolic Dynamics - the Minimal Shift Case
   Wit Foryś,  Piotr Oprocha 147-161
   We study interrelations between symbolic descriptions of concurrently evolving systems and underlying sequential dynamics. The basic framework for this research is formulated on the background of the theory of traces. We focus our interests on minimal shifts and t-shifts generated by them, that is shifts defined in the space of infinite real traces. We show that sets of infinite real traces generated by minimal shifts are always closed and, under some conditions, are also t-shifts. Additional discussion for the case of small alphabets (containing at most four letters) is also provided.
3. Weighted Extended Tree Transducers
   Zoltán Fülöp,  Andreas Maletti,  Heiko Vogler 163-202
   Weighted extended tree transducers (wxtts) over countably complete semirings are systematically explored. It is proved that the extension in the left-hand sides of a wxtt can be simulated by the inverse of a linear and nondeleting tree homomorphism. In addition, a characterization of the class of weighted tree transformations computable by bottom-up wxtts in terms of bimorphisms is provided. Backward and forward application to recognizable weighted tree languages are standard operations for wxtts. It is shown that the backward application of a linear wxtt preserves recognizability and that the domain of an arbitrary bottom-up wxtt is recognizable. Examples demonstrate that neither backward nor forward application of arbitrary wxtts preserves recognizability. Finally, a HASSE diagram relates most of the important subclasses of weighted tree transformations computable by wxtts.
4. Solution to the Range Problem for Combinatory Logic
   Benedetto Intrigila,  Richard Statman 203-222
   The l-theory H is obtained from b-conversion by identifying all closed unsolvable terms (or, equivalently, terms without head normal form). The range problem for the theory H asks whether a closed term has always (up to equality in H) either an infinite range or a singleton range (that is, it is a constant function). Here we give a solution to a natural version of this problem, giving a positive answer for the theory H restricted to Combinatory Logic. The method of proof applies also to the Lazy l-Calculus.
5. Rough Truth Degrees of Formulas and Approximate Reasoning in Rough Logic
   Yanhong She,  Xiaoli He,  Guojun Wang 223-239
   A propositional logic PRL for rough sets was proposed in [1]. In this paper, we initially introduce the concepts of rough (upper, lower) truth degrees on the set of formulas in PRL. Then, by grading the rough equality relations, we propose the concepts of rough (upper, lower) similarity degree. Finally, three different pseudo-metrics on the set of rough formulas are obtained, and thus an approximate reasoning mechanism is established.
6. Forward-Secure Identity-Based Public-Key Encryption without Random Oracles
   Jia Yu,  Fanyu Kong,  Xiangguo Cheng,  Rong Hao,  Jianxi Fan 241-256
   In traditional identity-based encryption schemes, security will be entirely lost once secret keys are exposed. However, with more and more use of mobile and unprotected devices, key exposure seems unavoidable. To deal with this problem, we newly propose a forward-secure identity-based public-key encryption scheme. In this primitive, the exposure of the secret key in one period doesn't affect the security of the ciphertext generated in previous periods. Any parameter in our scheme has at most log-squared complexity in terms of the total number of time periods. We also give the semantic security notions of forward-secure identity-based public-key encryption. The proposed scheme is proven semantically secure in the standard model. As far as we are concerned, it is the first forward-secure identity-based public-key encryption scheme without random oracles.

111(3) 2011

1. A Nonmonotonic Soft Concurrent Constraint Language to Model the Negotiation Process
   Stefano Bistarelli,  Francesco Santini 257-279
   We present an extension of the Soft Concurrent Constraint language that allows the nonmonotonic evolution of the constraint store. To accomplish this, we introduce some new operations: retract(c) reduces the current store by c, update_X(c) transactionally relaxes all the constraints of the store that deal with the variables in the set X, and then adds a constraint c; nask(c) tests if c is not entailed by the store. The new retraction operators also permit to reason about Belief Revision, i.e. the process of changing beliefs to take into account a new piece of information. We present this framework as a possible solution to the negotiation of resources (e.g. web services and network resource allocation) that need a given Quality of Service (QoS). For this reason we also show the the new operators of the language satisfy the Belief Revision postulates [20], which can be used in the negotiation process. The QoS requirements (expressed as semiring levels) of all the parties should converge on a formal agreement through a negotiation process, which specifies the contract that must be enforced.
2. Properties Complementary to Program Self-Reference
   John Case,  Samuel E. Moelius III 281-311
   In computability theory, program self-reference is formalized by the not-necessarily-constructive form of Kleene's Recursion Theorem (krt). In a programming system in which krt holds, for any preassigned, algorithmic task, there exists a program that, in a sense, creates a copy of itself, and then performs that task using the self-copy. Interpreted in this way, such self-copying programs have usable self-knowledge. Herein, properties complementary to krt are considered. Of particular interest are those properties involving the implementation of control structures . One main result is that no property involving the implementation of denotational control structures is complementary to krt. This is in contrast to a result of Royer, which showed that implementation of if-then-else - a denotational control structure - is complementary to the constructive form of Kleene's Recursion Theorem. Examples of non -denotational control structures whose implementation is complementary to krt are then given. Some such control structures so nearly resemble denotational control structures that they might be called quasi-denotational .
3. Self-Indexed Grammar-Based Compression
   Francisco Claude,  Gonzalo Navarro 313-337
   Self-indexes aim at representing text collections in a compressed format that allows extracting arbitrary portions and also offers indexed searching on the collection. Current self-indexes are unable of fully exploiting the redundancy of highly repetitive text collections that arise in several applications. Grammar-based compression is well suited to exploit such repetitiveness.
   We introduce the first grammar-based self-index. It builds on Straight-Line Programs (SLPs), a rather general kind of context-free grammars. If an SLP of n rules represents a text T[1,u], then an SLP-compressed representation of T requires 2nlog₂ n bits. For that same SLP, our self-index takes O(nlogn) + n log₂ u bits. It extracts any text substring of length m in time O((m+h)logn), and finds occ occurrences of a pattern string of length m in time O((m(m+h)+h occ)logn), where h is the height of the parse tree of the SLP. No previous grammar representation had achieved o(n) search time.
   As byproducts we introduce (i) a representation of SLPs that takes 2nlog₂ n (1+o(1)) bits and efficiently supports more operations than a plain array of rules; (ii) a representation for binary relations with labels supporting various extended queries; (iii) a generalization of our self-index to grammar compressors that reduce T to a sequence of terminals and nonterminals, such as Re-Pair and LZ78.
4. Runtime Monitoring of Contract Regulated Web Services
   Alessio Lomuscio,  Wojciech Penczek,  Monika Solanki,  Maciej Szreter 339-355
   We investigate the problem of locally monitoring contract regulated behaviours in agent-based web services. We encode contract clauses in service specifications by using extended timed automata. We propose a non intrusive local monitoring framework along with an API to monitor the fulfillment (or violation) of contractual obligations. A key feature of the framework is that it is fully symbolic thereby providing a scalable solution to monitoring. At runtime execution steps generated by the service are passed as input to the runtime monitor. Conformance of the execution against the service specification is checked using a symbolically represented extended timed automaton. This allows us to monitor service behaviours over large state spaces generated by multiple, long running contracts. We illustrate our methodology by monitoring a service composition scenario from the vehicle repair domain, and report on the experimental results.