bluuebunny/crossref_metadata_2025 huggingface dataset:
Capacity-Raising Steganography Using Multi-Pixel Differencing and	Pixel-Value Shifting Operations
Authors: Yang Cheng-Hsing , Wang Shiuh-Jeng , Weng Chi-Yao
Published: December 2019

In order to provide large embedding capacity and to minimize distortion for the stego-image, a steganographic method using multi-pixel differencing is presented in this paper. It takes into consideration four pixels of a block, and the differences between the lowest gray-value pixel and its surrounding pixels are used to determine the degree of smoothness and sharpness for embedding the secret data. If the difference values are large in a block, and the block is located in the sharp area then more data can be embedded. On the other hand, if the block is located in the smooth area less data can be embedded. The multi-pixel differencing method is employed in our scheme. We also propose the pixel-value shifting method to increase the image quality. The experimental results show that our scheme has a large embedding capacity without creating a noticeable distortion.
A Generic Approach to Connector Architectures Part I: The General Framework
Authors: Orejas Fernando , Ehrig Hartmut , Klein Markus , Padberg Julia , Pino Elvira , Pérez Sonia
Published: December 2019

The aim of this paper is to present a generic framework for the modelling of componentbased systems using architectural connectors. More precisely, concepts of component, connector and architecture are presented in a formal generic way, which are independent of any semi-formal or formal modelling approach. The idea is that one could use this framework to define component and connector notions for every given modelling formalism. As a main result, we define the semantics of architectures using graph transformation, showing that the semantics is independent of the order in which the connections are computed, and that the semantics is compatible with transformation. In the continuation of this paper, we show the applicability of our ideas. In particular, our framework is instantiated by Petri nets and CSP, including a case study using Petri Nets.
Computing Supports of Conjunctive Queries on Relational Tables	with Functional Dependencies
Authors: Jen Tao-Yuan , Laurent Dominique , Spyratos Nicolas
Published: December 2019

The problem of mining all frequent queries on a relational table is a problem known to be intractable even for conjunctive queries. In this article, we restrict our attention to conjunctive projection-selection queries and we assume that the table to be mined satisfies a set of functional dependencies. Under these assumptions, we define and characterize two pre-orderings with respect to which the support measure is shown to be anti-monotonic. Each of these pre-orderings induces an equivalence relation for which all queries of the same equivalence class have the same support. The goal of this article is not to provide algorithms for the computation of frequent queries, but rather to provide basic properties of pre-orderings and their associated equivalence relations showing that functional dependencies can be used for an optimized computation of supports of conjunctive queries. In particular, we show that one of the two pre-orderings characterizes anti-monotonicity of the support, while the other one refines the former, but allows to characterize anti-monotonicity with respect to a given table, only. Basic computational implications of these properties are discussed in the article.
Relational Contexts and Relational Concepts
Authors: Jiang Feng , Sui Yuefei , Cao Cungen
Published: December 2019

Formal concept analysis (FCA) is a mathematical description and theory of concepts implied in formal contexts. And the current formal contexts of FCA aim to model the binary relations between individuals (objects) and attributes in the real world. In the real world we usually describe each individual by some attributes, which induces the relations between individuals and attributes. But there also exist many relations between individuals, for instance, the parent-children relation in a family. In this paper, to model the relations between individuals in the real world, we propose a new context – relational context for FCA, which contains a set U of objects and a binary relation r on U. Corresponding to the formal concepts in formal contexts, we present different kinds of relational concepts in relational contexts, which are the pairs of sets of objects. First we define the standard relational concepts in relational contexts. Moreover, we discuss the indirect relational concepts and negative relational concepts in relational contexts, which aim to concern the indirection and negativity of the relations in relational contexts, respectively. Finally, we define the hybrid relational concepts in relational contexts, which are the combinations of any two different kinds of relational concepts. In addition, we also discuss the application of relational contexts and relational concepts in the supply chain management field.
Solvability of the Halting and Reachability Problem for Binary	2-tag Systems
Authors: De Mol Liesbeth
Published: December 2019

In this paper a detailed proofwill be given of the solvability of the halting and reachability problem for binary 2-tag systems.
Finding Patterns In Given Intervals
Authors: Crochemore Maxime , Kubica Marcin , Waleń Tomasz , Iliopoulos Costas S. , Rahman M. Sohel
Published: December 2019

In this paper, we study the pattern matching problem in given intervals. Depending on whether the intervals are given a priori for pre-processing, or during the query along with the pattern or, even in both the cases, we develop efficient solutions for different variants of this problem. In particular, we present efficient indexing schemes for each of the above variants of the problem.
Similarity-Based Classification in Relational Databases
Authors: Hońko Piotr
Published: December 2019

In this paper, we introduce a method for measuring similarity of objects of a relational database (relational objects, in short). We also propose and investigate an algorithm SC for classification of relational objects. The task of classification is carried out based on similarity of the objects to predefined classes. An object to be classified is assigned to the class to which it is most similar. A similarity of an object to a class is understood as its similarity to a class representative. Several methods for computing the class representative are proposed. We test the algorithm on real and artificial databases. We compare results obtained by the algorithm with those obtained by other algorithms known from the literature. We also present our approach in the context of granular computing.
An Improved Bound for an Extension of Fine and Wilf’s Theorem and Its Optimality
Authors: Kari Lila , Seki Shinnosuke
Published: December 2019

Considering two DNA molecules which are Watson-Crick (WK) complementary to each other “equivalent” with respect to the information they encode enables us to extend the classical notions of repetition, period, and power. WK-complementarity has been modelled mathematically by an antimorphic involution θ, i.e., a function θ such that θ(xy) = θ(y)θ(x) for any x, y ∞ Σ*, and θ2 is the identity. The WK-complementarity being thus modelled, any word which is a repetition of u and θ(u) such as uu, uθ(u)u, and uθ(u)θ(u)θ(u) can be regarded repetitive in this sense, and hence, called a θ-power of u. Taking the notion of θ-power into account, the Fine and Wilf’s theorem was extended as “given an antimorphic involution θ and words u, v, if a θ-power of u and a θ-power of v have a common prefix of length at least b(|u|, |v|) = 2|u| + |v| – gcd(|u|, |v|), then u and v are θ-powers of a same word.” In this paper, we obtain an improved bound b′(|u|, |v|) = b(|u|, |v|) – [gcd(|u|, |v|)/2]. Then we show all the cases when this bound is optimal by providing all the pairs of words (u, v) such that they are not θ-powers of a same word, but one can construct a θ-power of u and a θ-power of v whose maximal common prefix is of length equal to b′(|u|, |v|) − 1. Furthermore, we characterize such words in terms of Sturmian words.
Level Mapping Induced Loop Formulas for Weight Constraint and Aggregate Logic Programs
Authors: Liu Guohua , You Jia-Huai
Published: December 2019

Level mapping and loop formulas are two different means to justify and characterize answer sets for normal logic programs. Both of them specify conditions under which a supported model is an answer set. Though serving a similar purpose, in the past the two have been studied largely in isolation with each other. In this paper, we study level mapping and loop formulas for weight constraint and aggregate (logic) programs. We show that, for these classes of programs, loop formulas can be devised from level mapping characterizations. First, we formulate a level mapping characterization of stable models and show that it leads to a new formulation of loop formulas for arbitrary weight constraint programs, without using any new atoms. This extends a previous result on loop formulas for weight constraint programs, where weight constraints contain only positive literals. Second, since aggregate programs are closely related to weight constraint programs, we further use level mapping to characterize the underlying answer set semantics based on which we formulate loop formulas for aggregate programs. The main result is that for aggregate programs not involving the inequality comparison operator, the dependency graphs can be built in polynomial time. This compares to the previously known exponential time method.
Boruta – A System for Feature Selection
Authors: Kursa Miron B. , Jankowski Aleksander , Rudnicki Witold R.
Published: December 2019

Machine learning methods are often used to classify objects described by hundreds of attributes; in many applications of this kind a great fraction of attributes may be totally irrelevant to the classification problem. Even more, usually one cannot decide a priori which attributes are relevant. In this paper we present an improved version of the algorithm for identification of the full set of truly important variables in an information system. It is an extension of the random forest method which utilises the importance measure generated by the original algorithm. It compares, in the iterative fashion, the importances of original attributes with importances of their randomised copies. We analyse performance of the algorithm on several examples of synthetic data, as well as on a biologically important problem, namely on identification of the sequence motifs that are important for aptameric activity of short RNA sequences.
Enhancement of Multispectral Ikonos Satellite Image Using Quantum Information Processing
Authors: Shanker N.R. , Ramakrishnan S.S.
Published: December 2019

The objective of the paper is to demonstrate how an image enhancement technique denoted quantum Fourier transform, improves the possibilities for visual interpretation of multispectral IKONOS satellite image, covering an urban area. Image representation is usually based on a mathematical function that has two spatial values, x and y. The spatial points x and y in the image function have the values to represent intensity of the image at that spatial point. An alternative method of image representation is the transformation. Transformation is also a mathematical method in which an image is represented as complex exponential summations. The complex exponentials have the varying magnitudes, frequencies and phases. Transformation method of image representation is useful for image analysis, interpretations, filter etc. In this paper an image is represented based on the quantum mechanics for image analysis. The image is transformed using quantum Fourier transforms. For a specific application the result of processed image is better than the original image then it will be called as Enhancement. Enhancements of images are done in two broad categories. They are spatial domain methods and frequency domain methods. Frequency domain methods are based on transforms. And here quantum transforms is implemented. It is shown how the quantum Fourier transforms are applicable in the remote sensing satellite images, particularly for image enhancement. The satellite image of IKONOS is covering the Chennai city in Tamilnadu, India. From experimental result, it is observed that the pixels have low correlation when quantum Fourier transforms, are applied.
A Communication Approach to the Superposition Problem
Authors: Ablayev Farid , Ablayeva Svetlana
Published: December 2019

In function theory the superposition problem is known as the problem of representing a continuous function f(x1, … ,xk) in k variables as the composition of “simpler” functions. This problem stems from the Hilbert's thirteenth problem. In computer science good formalization for the notion of composition of functions is formula. In the paper we consider real-valued continuous functions in k variables in the cube [0,1]k from the class ℋkωp with ωp a special modulus of continuity (measure the smoothness of a function) defined in the paper. ℋkωp is a superset of Hölder class of functions. We present an explicit function f ∈ ℋkωp which is hard in the sense that it cannot be represented in the following way as a formula: zero level (input) gates associated with variables {x1, … ,xk} (different input gates can be associated with the same variable xi ∈ {x1, … ,xk}), on the first level of the formula, arbitrary number s ≥ 1 of t variable functions from ℋtωp for t < k are allowed, while the second (output) level may compute any s variable Hölder function. We apply communication complexity for constructing such hard explicit function. Notice that one can show the existence of such function using the “non constructive” proof method known in function theory as Kolmogorov's entropy method.
Synthesis and Complexity of Asymptotically Optimal Circuits with Unreliable Gates
Authors: Alekhina Marina An.
Published: December 2019

We consider the realization of Boolean functions by combinatorial circuits with unreliable gates computing the functions from a complete final basis B. We assume that all gates of the basis can have inverse faults on the outputs independently with probability ε (ε ∈ (0, 1/2)). We describe a set Mk (k ≥ 3) of Boolean functions, presence even by one of which in basis B guarantees the computing of almost all Boolean functions by asymptotically optimal circuits with unreliability ε at ε → 0. We prove that, for almost all functions, the complexity of asymptotically circuits with unreliable gates exceeds the complexity of the minimal circuits constructed from absolutely reliable gates by a multiplicative factor of 3(1 + b) for any b > 0.
High Accuracy Asymptotic Bounds on the BDD Size and Weight of the Hardest Functions
Authors: Lozhkin Sergei A. , Shiganov Alexander E.
Published: December 2019

In this paper we study the representation of Boolean functions by general binary decision diagrams (BDDs). We investigate the size L(Σ) (number of inner nodes) of BDD Σ with different constraints on the number M(Σ) of its merged nodes. Furthermore, we introduce a weighted complexity measure W(Σ) = L(Σ) + ωM(Σ), where ω > 0. For the hardest Boolean function on n input variables we define the weight WBDD(n) and the size LBDD(n,t), where t limits the number of merged nodes. By using a new synthesis method and appropriate restrictions for the number t of merged nodes, we are able to prove tight upper and lower asymptotic bounds: WBDD(n) = 2n/n (1 + log n ± O(1)/n), LBDD(n,t) = 2n/log nt (1 ± O(1/n)), which have a relative error of O(1/n). Our results show how weight and structural restrictions of general BDDs influence the complexity of the hardest function in terms of high accuracy asymptotic bounds.
Greedy Algorithm with Weights for Decision Tree Construction
Authors: Moshkov Mikhail Ju.
Published: December 2019

An approximate algorithm for minimization of weighted depth of decision trees is considered. A bound on accuracy of this algorithm is obtained which is unimprovable in general case. Under some natural assumptions on the class NP, the considered algorithm is close (from the point of view of accuracy) to best polynomial approximate algorithms for minimization of weighted depth of decision trees.
Horn Knowledge Bases in Regular Description Logics with PTIME Data Complexity
Authors: Nguyen Linh Anh
Published: December 2019

Developing a good formalism and an efficient decision procedure for the instance checking problem is desirable for practical application of description logics. The data complexity of the instance checking problem is coNP-complete even for Horn knowledge bases in the basic description logic ALC. In this paper, we present and study weakenings with PTIME data complexity of the instance checking problem for Horn knowledge bases in regular description logics. We also study cases when the weakenings are an exact approximation. In contrast to previous related work of other authors, our approach deals with the case when the constructor ∀ is allowed in premises of program clauses that are used as terminological axioms.
Breaking Pomykala-Barabasz Threshold Proxy Signature Scheme
Authors: Shao Zuhua
Published: December 2019

In 2006, Pomykala and Barabasz proposed an elliptic curve based threshold proxy signature scheme with known signers. They claimed that their scheme was relatively simple in construction, had the properties of unforgeability and non-repudiation, and admitted the proactive security. Later, Li and Hu pointed out that the scheme of Pomykala and Barabasz was insecure against the conspiracy attack. And then, they proposed an improved scheme. In this paper, we not only show that the threshold proxy signature scheme of Pomykala and Barabasz is universal forgeable, but also show that the improvement of Li and Hu suffers from the rogue key attack.
Equational Reasoning on Mobile Ad Hoc Networks
Authors: Ghassemi Fatemeh , Fokkink Wan , Movaghar Ali
Published: December 2019

We provide an equational theory for Restricted Broadcast Process Theory to reason about ad hoc networks. We exploit an extended algebra called Computed Network Theory to axiomatize restricted broadcast. It allows one to define the behavior of an ad hoc network with respect to the underlying topologies. We give a sound and ground-complete axiomatization for CNT terms with finite-state behavior, modulo what we call rooted branching computed network bisimilarity.
A Paraconsistent Linear-time Temporal Logic
Authors: Kamide Norihiro , Wansing Heinrich
Published: December 2019

Inconsistency-tolerant reasoning and paraconsistent logic are of growing importance not only in Knowledge Representation, AI and other areas of Computer Science, but also in Philosophical Logic. In this paper, a new logic, paraconsistent linear-time temporal logic (PLTL), is obtained semantically from the linear-time temporal logic LTL by adding a paraconsistent negation. Some theorems for embedding PLTL into LTL are proved, and PLTL is shown to be decidable. A Gentzentype sequent calculus PLTω for PLTL is introduced, and the completeness and cut-elimination theorems for this calculus are proved. In addition, a display calculus δPLTω for PLTL is defined.
Unsupervised and Supervised Learning Approaches Together for Microarray Analysis
Authors: Saha Indrajit , Maulik Ujjwal , Bandyopadhyay Sanghamitra , Plewczynski Dariusz
Published: December 2019

In this article, a novel concept is introduced by using both unsupervised and supervised learning. For unsupervised learning, the problem of fuzzy clustering in microarray data as a multiobjective optimization is used, which simultaneously optimizes two internal fuzzy cluster validity indices to yield a set of Pareto-optimal clustering solutions. In this regards, a new multiobjective differential evolution based fuzzy clustering technique has been proposed. Subsequently, for supervised learning, a fuzzy majority voting scheme along with support vector machine is used to integrate the clustering information from all the solutions in the resultant Pareto-optimal set. The performances of the proposed clustering techniques have been demonstrated on five publicly available benchmark microarray data sets. A detail comparison has been carried out with multiobjective genetic algorithm based fuzzy clustering, multiobjective differential evolution based fuzzy clustering, single objective versions of differential evolution and genetic algorithm based fuzzy clustering as well as well known fuzzy c-means algorithm. While using support vector machine, comparative studies of the use of four different kernel functions are also reported. Statistical significance test has been done to establish the statistical superiority of the proposed multiobjective clustering approach. Finally, biological significance test has been carried out using a web based gene annotation tool to show that the proposed integrated technique is able to produce biologically relevant clusters of coexpressed genes.
Application of the Method of Editing and Condensing in the Process of Global Decision-making
Authors: Wakulicz-Deja Alicja , Przybyła-Kasperek Małgorzata
Published: December 2019

The paper presents the process of taking global decisions on the basis of the knowledge of local decision systems, in which sets of conditional attributes are different but not necessarily disjoint. We propose the organization of local decision systems into a multi-agent system with a hierarchical structure. The structure of multi-agent systems and the theoretical aspects of the organization of the system are presented. An editing and a condensing algorithm have been used in the process of global decision making. Also a density-based algorithm has been used in the process of taking global decisions to resolve conflicts. Furthermore, the paper presents the results of experiments conducted using some data sets from UCI repository.
K-Comma Codes and Their Generalizations
Authors: Cui Bo , Kari Lila , Seki Shinnosuke
Published: December 2019

In this paper, we introduce the notion of k-comma codes - a proper generalization of the notion of comma-free codes. For a given positive integer k, a k-comma code is a set L over an alphabet Σ with the property that LΣkL ∩ Σ+LΣ+ = ∅. Informally, in a k-comma code, no codeword can be a subword of the catenation of two other codewords separated by a “comma” of length k. A k-comma code is indeed a code, that is, any sequence of codewords is uniquely decipherable. We extend this notion to that of k-spacer codes, with commas of length less than or equal to a given k. We obtain several basic properties of k-comma codes and their generalizations, k-comma intercodes, and some relationships between the families of k-comma intercodes and other classical families of codes, such as infix codes and bifix codes. Moreover, we introduce the notion of n-k-comma intercodes, and obtain, for each k ≥ 0, several hierarchical relationships among the families of n-k-comma intercodes, as well as a characterization of the family of 1-k-comma intercodes.
Analysis of Recognition of a Musical Instrument in Sound Mixes Using Support Vector Machines
Authors: Wieczorkowska Alicja , Kubera Elżbieta , Kubik-Komar Agnieszka
Published: December 2019

Experiments with recognition of the dominating musical instrument in sound mixes are interesting from the point of view of music information retrieval, but this task can be very difficult if the mixed sounds are of the same pitch. In this paper, we analyse experiments on recognition of the dominating instrument in mixes of same-pitch sounds of definite pitch. Sound from one octave (no. 4 in MIDI notation) have been chosen, and instruments of various types, including percussive instruments were investigated. Support vector machines were used in our experiments, and statistical analysis of the results was also carefully performed. After discussing the outcomes of these experiments and analyses, we conclude our paper with suggestions regarding directions of possible future research on this subject.
A Representation Theorem for Primitive Recursive Algorithms
Authors: Andary Philippe , Patrou Bruno , Valarcher Pierre
Published: December 2019

We formalize the algorithms computing primitive recursive (PR) functions as the abstract state machines (ASMs) whose running length is computable by a PR function. Then we show that there exists a programming language (implementing only PR functions) by which it is possible to implement any one of the previously defined algorithms for the PR functions in such a way that their complexity is preserved.
On the Fermat-Weber Point of a Polygonal Chain and its Generalizations
Authors: Bhattacharya Bhaswar B.
Published: December 2019

In this paper, we study the properties of the Fermat-Weber point for a set of fixed points, whose arrangement coincides with the vertices of a regular polygonal chain. A k-chain of a regular n-gon is the segment of the boundary of the regular n-gon formed by a set of k (≤ n) consecutive vertices of the regular n-gon. We show that for every odd positive integer k, there exists an integer N(k), such that the Fermat-Weber point of a set of k fixed points lying on the vertices a k-chain of a n-gon coincides with a vertex of the chain whenever n ≥ N(k). We also show that $\lceil$πm(m + 1) - π2/4$\rceil$ ≤ N(k) ≤ $\lfloor$πm(m + 1) + 1$\rfloor$, where k (= 2m + 1) is any odd positive integer. We then extend this result to a more general family of point set, and give an O(hk log k) time algorithm for determining whether a given set of k points, having h points on the convex hull, belongs to such a family.
Constraint Satisfaction Problems in Clausal Form I: Autarkies and Deficiency
Authors: Kullmann Oliver
Published: December 2019

We consider the problem of generalising boolean formulas in conjunctive normal form by allowing non-boolean variables, with the goal of maintaining combinatorial properties. Requiring that a literal involves only a single variable, the most general form of literals are the wellknown “signed literals”, corresponding to unary constraints in CSP. However we argue that only the restricted form of “negative monosigned literals” and the resulting generalised clause-sets, corresponding to “sets of no-goods” in the AI literature, maintain the essential properties of boolean conjunctive normal forms. In this first part of a mini-series of two articles, we build up a solid foundation for (generalised) clause-sets, including the notion of autarky systems, the interplay between autarkies and resolution, and basic notions of (DP-)reductions. As a basic combinatorial parameter of generalised clause-sets we introduce the (generalised) notion of deficiency, which in the boolean case is the difference between the number of clauses and the number of variables. Autarky theory plays a fundamental role here, and we concentrate especially on matching autarkies (based on matching theory). A natural task is to determine the structure of (matching) lean clause-sets, which do not admit non-trivial (matching) autarkies. A central result is the computation of the lean kernel (the largest lean subset) of a (generalised) clause-set in polynomial time for bounded maximal deficiency.
An Operational Petri Net Semantics for A2CCS
Authors: Gorrieri Roberto , Versari Cristian
Published: December 2019

A2CCS is a conservative extension of CCS, enriched with an operator of strong prefixing, enabling the modeling of atomic sequences and multi-party synchronization (realized as an atomic sequence of binary synchronizations); the classic dining philosophers problem is used to illustrate the approach. A step semantics for A2CCS is also presented directly as a labeled transition system. A safe Petri net semantics for this language is presented, following the approach of Degano, De Nicola, Montanari and Olderog. We prove that a process p and its associated net Net(p) are interleaving bisimilar (Theorem 5.1). Moreover, to support the claim that the intended concurrency is well-represented in the net, we also prove that a process p and its associated net Net(p) are step bisimilar (Theorem 5.2).
Typical Paths of a Graph
Authors: Cui Cewei , Dang Zhe , Fischer Thomas R.
Published: December 2019

We introduce (finite and infinite) typical paths of a graph and prove that the typical paths carry all information with probability 1, asymptotically. An automata-theoretic characterization of the typical paths is shown: finite typical paths can be accepted by reversal-bounded multicounter automata and infinite typical paths can be accepted by counting Büchi automata (a generalization of reversal-bounded multicounter automata running on ω-words). We take a statechart example to show how to generate typical paths from a graph using SPIN model checker. The results are useful in automata theory since one can identify an information-concentrated-core of a regular language such that only words in the information-concentrated-core carry nontrivial information. When the graph is used to specify the system under test, the results are also useful in software testing by providing an information-theoretic approach to select test cases that carry nontrivial information of the system specification.
Hierarchies of Stateless Multicounter 5′ → 3′ Watson-Crick Automata Languages
Authors: Eğecioğlu Ömer , Hegedüs Lászl´ , Nagy Benedek
Published: December 2019

We consider stateless counter machines which mix the features of one-head counter machines and a special type of two-head Watson-Crick automata (WK-automata). Our Watson-Crick counter machines are biologically motivated. They have two heads that read the input starting from the two extremes. The reading process is finished when there are no more symbols between the heads, i.e., every letter of the input is processed by either head. Depending on whether the heads are required to advance at each move, we distinguish between realtime and non-realtime machines. If every counter makes at most k alternations between nondecreasing and decreasing modes in every computation, then the machine is k-reversal. It is reversal bounded if it is k-reversal for some k. In this paper we concentrate on the properties of both deterministic and nondeterministic stateless WK-automata with reversal bounded counters.
On the Regularity of Iterated Hairpin Completion of a Single Word
Authors: Kari Lila , Seki Shinnosuke , Kopecki Steffen
Published: December 2019

Hairpin completion is an abstract operation modeling a DNA bio-operation which receives as input a DNA strand w = xαy\bar{α}, and outputs w' = xαy\bar{α}\bar{x}, where \bar{x} denotes the Watson-Crick complement of x. In this paper, we focus on the problem of finding conditions under which the iterated hairpin completion of a given word is regular. According to the numbers of words α and \bar{α} that initiate hairpin completion and how they are scattered, we classify the set of all words w. For some basic classes of words w containing small numbers of occurrences of α and \bar{α}, we prove that the iterated hairpin completion of w is regular. For other classes with higher numbers of occurrences of α and \bar{α}, we prove a necessary and sufficient condition for the iterated hairpin completion of a word in these classes to be regular.
On the Hairpin Incompletion
Authors: Okubo Fumiya , Yokomori Takashi
Published: December 2019

Hairpin completion and its variant called bounded hairpin completion are operations on formal languages, inspired by a hairpin formation in molecular biology. Another variant called hairpin lengthening has been recently introduced, and the related closure properties and algorithmic problems concerning several families of languages have been studied. In this paper, we introduce a new operation of this kind, called hairpin incompletion which is not only an extension of bounded hairpin completion, but also a restricted (bounded) variant of hairpin lengthening. Further, the hairpin incompletion operation provides a formal language theoretic framework that models a bio-molecular technique nowadays known as Whiplash PCR. We study the closure properties of language families under both the operation and its iterated version. We show that a family of languages closed under intersection with regular sets, concatenation with regular sets, and finite union is closed under one-sided iterated hairpin incompletion, and that a family of languages containing all linear languages and closed under circular permutation, left derivative and substitution is also closed under iterated hairpin incompletion.
Runtime Monitoring of Contract Regulated Web Services
Authors: Lomuscio Alessio , Penczek Wojciech , Solanki Monika , Szreter Maciej
Published: December 2019

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.
A Lower Bound of the Second–order Nonlinearities of Boolean Bent Functions
Authors: Garg Manish , Gangopadhyay Sugata
Published: December 2019

In this paper we find a lower bound of the second-order nonlinearities of Boolean bent functions of the form ${\rm f}({\rm x}) = {\rm Tr}_{1}^{{\rm n}}(\rmalpha_{1}{\rm x}^{{\rm d}_{1}} + \rmalpha_{2}{\rm x}^{{\rm d}_{2}})$, where d1 and d2 are Niho exponents. A lower bound of the second-order nonlinearities of these Boolean functions can also be obtained by using a recent result of Li, Hu and Gao (eprint.iacr.org/2010 /009.pdf). It is shown in Section 3, by a direct computation, that for large values of n, the lower bound obtained in this paper are better than the lower bound obtained by Li, Hu and Gao.
Blackhole Pushdown Automata
Authors: Csuhaj-Varjú Erzsébet , Masopust Tomáš , Vaszil György
Published: December 2019

We introduce and investigate blackhole pushdown automata, variants of pushdown automata, where a string can always be pushed to the pushdown, but only a given depth of the pushdown content is remembered (the rest of the pushdown content is either canceled or becomes inaccessible). We also study blackhole variants of regulated pushdown automata, where the automaton in some distinguished states checks the form of its pushdown content against a given control language. We present characterizations of several language families in terms of these constructs.
Growing Grammars and Length-reducing Automata
Authors: Jurdziński Tomasz
Published: December 2019

Growing context-sensitive grammars were introduced in 1986 as a restricted variant of context-sensitive grammars, where all productions are length increasing. Several interesting properties of these grammars have been shown since then, including polynomial time complexity of the membership problem and machine model characterizations. Various characterizations of the model, efficient recognition algorithm and the properties of its deterministic variant (possessing a characterization by string-rewriting systems) justify the practical value. Moreover, as pointed out by McNaughton in 1999, growing context-sensitive grammars complement the Chomsky hierarchy in a very natural way. This article reviews results on this topic and proposes some open problems.
Rough Approximations in Varieties of Regular Languages
Authors: Martin Gabriela , Steinby Magnus
Published: December 2019

We study approximations of regular languages bymembers of a given variety ℒ of regular languages. These are upper or lower approximations in the sense of Pawlak's rough set theory with respect to congruences belonging to the variety of congruences corresponding to ℒ. In particular, we consider the closest upper and lower approximations in ℒ. In so-called principal varieties these always exist, and we present algorithms for finding them, but for other varieties the situation is more complex. Although we consider just Eilenberg’s +-varieties, the general ideas apply also to other types of varieties of languages. Our work may also be viewed as an approach to the characterizable inference problem in which a language of a certain kind is to be inferred from a given sample.
Algebraic Framework for the Specification and Analysis of Cryptographic-Key Distribution
Authors: Sabri Khair Eddin , Khedri Ridha
Published: December 2019

Several organizations generate and store a wide range of information in what is commonly referred to as data stores. To access the information within these data stores, two main architectures are widely adopted. The first architecture gives access to information through a trusted server that enforces established confidentiality policies. The second one allows the information to be public but in its encrypted form. Then through a scheme for the distribution of cryptographic keys, each user is provided with the keys needed to decrypt only the part of the information she is authorized to access. This paper relates to the latter architecture. We introduce an algebraic framework that takes into consideration a new perspective in tackling the key-distribution problem. We use the proposed framework to analyze key-distribution schemes that are representative of the ones found in the literature. The framework enables the specification and the verification of key-distribution policies. We also point to several other applications related to measures ensuring information confidentiality.
Security Pitfalls of the Certificateless Signature and Multi-Receiver Signcryption Schemes
Authors: Shim Kyung-Ah , Lee Young-Ran
Published: December 2019

Recently, Xiong et al. and Selvi et al. proposed a certificateless signature scheme secure in the standard model and a certificateless multi-receiver signcryption scheme secure in the random oracle model, respectively. In this paper, we show that they are insecure against malicious-butpassive KGC attacks. More specifically, the former does not achieve unforgeability and the latter does not satisfy confidentiality against type II adversaries.
Public Announcement Logic in Geometric Frameworks
Authors: Başkent Can
Published: December 2019

In this paper, we introduce public announcement logic in different geometric frameworks. First, we consider topological models, and then extend our discussion to a more expressive model, namely, subset space models. Furthermore, we prove the completeness of public announcement logic in those frameworks. After that, we apply our results to different issues: announcement stabilization, backward induction and persistence.
Tree Matrices and a Matrix Reduction Algorithm of Belitskii
Authors: Grzecza Marcin , Kasjan Stanisław , Mróz Andrzej
Published: December 2019

Inspired by the bimodule matrix problem technique and various classification problems in poset representation theory, finite groups and algebras, we study the action of Belitskii algorithm on a class of square n by n block matrices M with coefficients in a field K. One of the main aims is to reduce M to its special canonical form M∞ with respect to the conjugation by elementary transformations defined by a class of matrices chosen in a subalgebra of the full matrix algebra $\mathbb{M}_n$(K). The algorithm can be successfully applied in the study of indecomposable linear representations of finite posets by a computer search using numeric and symbolic computation. We mainly study the case when the di-graph (quiver) associated to the output matrix M∞ of the algorithm is a disjoint union of trees. We show that exceptional representations of any finite poset are determined by tree matrices. This generalizes a theorem of C.M. Ringel proved for linear representations of di-graphs.
Reversible Data Hiding Scheme Based on Image Inpainting
Authors: Qin Chuan , Wang Zhi-Hui , Chang Chin-Chen , Chen KuoNan
Published: December 2019

Reversible/lossless image data hiding schemes provide the capability to embed secret information into a cover image where the original carrier can be totally restored after extracting the secret information. This work presents a high performance reversible image data hiding scheme especially in stego image quality control using image inpainting, an efficient image processing skill. Embeddable pixels chosen from a cover image are initialized to a fixed value as preprocessing for inpainting. Subsequently, these initialized pixels are repaired using inpainting technique based on partial differential equations (PDE). These inpainted pixels can be used to carry secret bits and generate a stego image. Experimental results show that the proposed scheme produces low distortion stego images and it also provides satisfactory hiding capacity.
On the Behaviours Produced by Instruction Sequences under Execution
Authors: Bergstra J.A. , Middelburg C.A.
Published: December 2019

We study several aspects of the behaviours produced by instruction sequences under execution in the setting of the algebraic theory of processes known as ACP. We use ACP to describe the behaviours produced by instruction sequences under execution and to describe two protocols implementing these behaviours in the case where the processing of instructions takes place remotely. We also show that all finite-state behaviours considered in ACP can be produced by instruction sequences under execution.
Variance as a Stopping Criterion for Genetic Algorithms with Elitist Model
Authors: Bhandari Dinabandhu , Murthy C. A. , Pal Sankar K.
Published: December 2019

Genetic Algorithm (GA) has now become one of the leading mechanisms in providing solution to complex optimization problems. Although widely used, there are very few theoretical guidelines for determining when to stop the algorithm. This article establishes theoretically that the variance of the best fitness values obtained in the iterations can be considered as a measure to decide the termination criterion of a GA with elitist model (EGA). The criterion automatically takes into account the inherent characteristics of the objective function. Implementation issues of the proposed stopping criterion are explained. Its difference with some other stopping criteria is also critically analyzed.
Computing Issues of Asynchronous CA
Authors: Dennunzio Alberto , Formenti Enrico , Manzoni Luca
Published: December 2019

This work studies some aspects of the computational power of fully asynchronous cellular automata (ACA). We deal with some notions of simulation between ACA and Turing Machines. In particular, we characterize the updating sequences specifying which are “universal”, i.e., allowing a (specific family of) ACA to simulate any Turing machine on any input. We also consider the computational cost of such simulations. Finally, we deal with ACA equipped with peculiar updating sequences, namely those generated by random walks.
Making DNA Expressions Minimal
Authors: van Vliet Rudy , Hoogeboom Hendrik Jan
Published: December 2019

DNA expressions constitute a formal notation for DNA molecules that may contain nicks and gaps. Different DNA expressions may denote the same DNA molecule. We describe an algorithm to rewrite a given DNA expression into a DNA expression of minimal length denoting the same molecule.
A Minimal Normal Form for DNA Expressions
Authors: van Vliet Rudy , Hoogeboom Hendrik Jan
Published: December 2019

DNA expressions constitute a formal notation for DNA molecules that may contain nicks and gaps. Different DNA expressions may denote the same DNA molecule. We define a (minimal) normal form for the language of DNA expressions, and describe an algorithm to rewrite a given DNA expression into the normal form.
A Comparative Study of Ordered and Covering Information Systems
Authors: Wang Changzhong , Chen Degang , He Qiang , Hu Qinhua
Published: December 2019

Covering information systems and ordered information systems are two important types of information systems. In this paper the relationships between covering information systems and ordered information systems are first examined, and it is proved that these two types of information systems are isomorphic under given conditions and can be equivalently transformed into each other. Then, the approach to attribute reduction in ordered information systems is proposed. Based on the isomorphism and equivalence of transformation, the method of attribute reduction in a covering information system can be directly obtained according to the reduction approach in an ordered information system. A practical example is employed to show that the proposed method is an effective technique to deal with complex data sets.
On Characterizing Hierarchies of Granulation Structures via Distances
Authors: Yang Xibei , Qian Yuhua , Yang Jingyu
Published: December 2019

Hierarchy plays a crucial role in the development of the granular computing. In this paper, three different hierarchies are considered for judging whether a granulation structure is finer or coarser than another one. The first hierarchy is based on the set containment of information granulations, the second hierarchy is based on the cardinal numbers of information granulations while the third hierarchy is based on the sum of cardinal numbers of information granulations. Through introducing set distance and knowledge distance, we investigate the algebraic lattices, in which the derived partial orders are corresponding to the three different hierarchies, respectively. From the viewpoint of distance, these results look forward to provide a more comprehensible perspective for the study of hierarchies on granulation structures.