bluuebunny/crossref_metadata_2025 huggingface dataset:
Decision Trees for Regular Language Word Recognition
Authors: Moshkov Mikhail
Published: December 2019

In this paper the problem of recognition of words with fixed length from a regular language is considered. The word under consideration can be interpreted as a description of certain screen image in the following way: the i-th letter of the word encodes the color of the i-th screen cell. In this case a decision tree which recognizes some words may be interpreted as an algorithm for the recognition of images which are defined by considered words. The classification of all regular languages depending on the growth of minimal depth of decision trees for language word recognition with the growth of the word length is obtained. In proofs methods of test theory and rough set theory are used.
Constructing the Least Models for Positive Modal Logic Programs
Authors: Nguyen Linh Anh
Published: December 2019

We give algorithms to construct the least L-model for a given positive modal logic program P, where L can be one of the modal logics KD, T, KDB, B, KD4, S4, KD5, KD45, and S5. If L ∈ {KD5,KD45,S5}, or L ∈ {KD,T,KDB,B} and the modal depth of P is finitely bounded, then the least L-model of P can be constructed in PTIME and coded in polynomial space. We also show that if P has no flat models then it has the least models in KB, K5, K45, and KB5. As a consequence, the problem of checking the satisfiability of a set of modal Horn formulae with finitely bounded modal depth in KD, T, KB, KDB, or B is decidable in PTIME. The known result that the problem of checking the satisfiability of a set of Horn formulae in K5, KD5, K45, KD45, KB5, or S5 is decidable in PTIME is also studied in this work via a different method.
Models For Dependable Computation with Multiple Inputs and Some Hardness Results
Authors: Wang Yongge , Desmedt Yvo , Burmester Mike
Published: December 2019

We consider the problem of dependable computation with multiple inputs. The goal is to study when redundancy can help to achieve survivability and when it cannot. We use AND/OR graphs to model fault tolerant computations with multiple inputs. While there is a polynomial time algorithm for finding vertex disjoint paths in networks, we will show that the equivalent problem in computation systems with multiple inputs is NP-hard. Our main results are as follows. (1) We present a general model for fault tolerant computation systems with multiple inputs: AND/OR graphs. (2) We show that it is NP-hard to find two vertex disjoint solution graphs in an AND/OR graph. It follows that in the general case redundancy cannot help to achieve survivability, assuming P≠NP.
An Algebra of Data Flows
Authors: Winkowski Józef
Published: December 2019

An algebra of processes is proposed in which processes are modelled in terms of data rather than events. Structures representing processes are similar to the labelled event structures of Winskel (1982), but they denote flows of data. For processes represented in such a way operations similar to those of CCS (the Calculus of Communicating Systems as developed by Milner (1980)) are defined and their fundamental properties are stated.
Reliable Minimum Finding Comparator Networks
Authors: Denejko Piotr , Diks Krzysztof , Pelc Andrzej , Piotrów Marek
Published: December 2019

We consider the problem of constructing reliable comparator networks built from unreliable comparators. In case of a faulty comparator inputs are directly output without comparison. A trivial lower bound of Ω(logn + k) on the depth of n-input k-fault tolerant sorting network is well known. We are interested in establishing exact lower bounds on the depth of such networks. To this end we consider fairly simple minimum-finding networks. Our main result is the first nontrivial lower bound on depths of networks computing minimum among n > 2 items in the presence of k > 0 faulty comparators. We prove that the depth of any such network is at least max([logn] + 2k, logn + klog logn/k+1). We also describe a network whose depth nearly matches the lower bound.
Necessity Measures and Parametric Inclusion Relations of Fuzzy Sets
Authors: Inuiguchi Masahiro , Tanino Tetsuzo
Published: December 2019

A necessity measure N is defined by an implication function. However, specification of an implication function is difficult. Necessity measures are closely related to inclusion relations. In this paper, we propose an approach to necessity measure specification by giving a parametric inclusion relation between fuzzy sets A and B which is equivalent to NA(B) ≥ h. It is shown that, in such a way, we can specify a necessity measure, i.e., an implication function. Moreover, when a necessity measure or equivalently, an implication function is given, then the derivation of an associated parametric inclusion relation is discussed. The associated parametric inclusion relation cannot be obtained for any implication function but only for implication functions which satisfy certain conditions. Applying our results to necessity measures defined by S-, R- and reciprocal R-implications with continuous Archimedean t-norms, associated parametric inclusion relations are shown.
First-order Non-monotonic Modal Logics
Authors: Kaminski Michael , Rey Guy
Published: December 2019

In this paper we introduce first-order non-monotonic modal logic and study its properties. Our definition is semantical and is based on the intuition similar to that lying behind the definition of first-order default logic. Thus, our definition of first-order non-monotonic modal logic well complies with that of first-order default logic and circumscription, providing a substantial evidence for its acceptance. In addition, our definition implies all properties of propositional non-monotonic modal logic, which supplies an additional support for its adequacy.
Finite Completeness of Categories of Petri Nets
Authors: Bednarczyk Marek A. , Borzyszkowski Andrzej M. , Somla Rafał
Published: December 2019

The problem of finite completeness of categories of Petri nets is studied. Since Petri nets have finite products, the problem reduces to the issue of the existence of equalizers. We show that the categories of Petri nets with general and Winskel morphisms do not admit equalizers, and hence are not finitely complete. The main positive result of the paper states that reachable Petri nets with multiplicative morphisms form a finitely complete category. As an application of this result, some well-known categories are shown to be finitely complete. For instance, since all morphisms between reachable safe Petri nets are multiplicative, it follows that the category of reachable safe Petri nets is finitely complete.
Nested Petri Nets — a Formalism for Specification and Verification of Multi-Agent Distributed Systems
Authors: Lomazova Irina A.
Published: December 2019

Nested Petri nets is a formalism for modeling hierarchical multi-agent systems. Tokens in nested Petri nets are elements represented by nets themselves. Decidability of some crucial for verification problems shows that, in spite of their ”unflat” structure, nested Petri nets maintain significant properties of ordinary Petri nets. A comparison with some other Petri net models is given. The formalism allows generalization to a recursive case, when a nested Petri net may generate its own copy as its element. Two simple examples illustrate the approach.
A Simple Implementation of Dijkstra's Shortest Path Algorithm on Associative Parallel Processors
Authors: Nepomniaschaya Anna S. , Dvoskina Maria A.
Published: December 2019

In this paper we propose a natural straight forward implementation of Dijkstra's shortest path algorithm on a model of associative parallel processors of the SIMD type with bit-serial (or vertical) processing (the STAR-machine). In addition, we show how to extend this implementation for restoring the shortest path from the source vertex to a given vertex. These algorithms of implementation are represented as the corresponding STAR procedures whose correctness is verified and time complexity is evaluated.
Improving Partial Order Reductions for Universal Branching Time Properties
Authors: Penczek Wojciech , Szreter Maciej , Gerth Rob , Kuiper Ruurd
Published: December 2019

The ”state explosion problem” can be alleviated by using partial order reduction techniques. These methods rely on expanding only a fragment of the full state space of a program, which is sufficient for verifying the formulas of temporal logics LTL−X or CTL−X*(i.e., LTL or CTL* without the next state operator). This is guaranteed by preserving either a stuttering maximal trace equivalence or a stuttering bisimulation between the full and the reduced state space. Since a stuttering bisimulation is much more restrictive than a stuttering maximal trace equivalence, resulting in less powerful reductions for CTL−X*, we study here partial order reductions that preserve equivalences ”in-between”, in particular a stuttering simulation which is induced by the universal fragment of CTL:−X*, called ACTL−X* The reductions generated by our method preserve also branching simulation and weak simulation, but surprisingly, they do not appear to be included into the reductions obtained by Peled's method for verifying LTL−X properties. Therefore, in addition to ACTL−X* reduction method we suggest also an improvement of the LTL−X reduction method. Moreover, we prove that reduction for concurrency fair version of ACTL−X* is more efficient than for ACTL−X*.
An Application of Rough Set Methods in Control Design
Authors: Peters James F. , Skowron Andrzej , Suraj Zbigniew
Published: December 2019

The paper deals with an automatic concurrent control design method derived from the specification of a discrete event control system represented in the form of a decision table. The main stages of our approach are: the control specification by decision tables, generation of rules from the specification of the system behavior, and converting rules set into a concurrent program represented in the form of a Petri net. Our approach is based on rough set theory [17].
Analyzing and Reducing Simultaneous Firing in Signal-Event Nets
Authors: Roch Stephan
Published: December 2019

Signal-event nets provide a modular modeling technique based on Petri nets. Actions of a module can be activated or can be prevented by another module through condition arcs. One-sided synchronization of modules is done by signal-events, which cause the execution of actions in steps. But due to condition arcs and signal-events simultaneous firing of steps may lead to markings, which are not reachable by conventional sequential interleaving. We give a criterion, in which situations simultaneous firing of steps can be safely omitted, without missing reachable markings.
A General Similarity Framework for Horn Clause Logic
Authors: Ferilli S. , Basile T.M.A. , Biba M. , Di Mauro N. , Esposito F.
Published: December 2019

First-Order Logic formulæ are a powerful representation formalism characterized by the use of relations, that cause serious computational problems due to the phenomenon of indeterminacy (various portions of one description are possibly mapped in different ways onto another description). Being able to identify the correct corresponding parts of two descriptions would help to tackle the problem: hence, the need for a framework for the comparison and similarity assessment. This could have many applications in Artificial Intelligence: guiding subsumption procedures and theory revision systems, implementing flexible matching, supporting instance-based learning and conceptual clustering. Unfortunately, few works on this subject are available in the literature. This paper focuses on Horn clauses, which are the basis for the Logic Programming paradigm, and proposes a novel similarity formula and evaluation criteria for identifying the descriptions components that are more similar and hence more likely to correspond to each other, based only on their syntactic structure. Experiments on real-world datasets prove the effectiveness of the proposal, and the efficiency of the corresponding implementation in the above tasks.
Statistical Independence and Determinants in a Contingency Table	– Interpretation of Pearson Residuals based on Linear Algebra –
Authors: Tsumoto Shusaku , Hirano Shoji
Published: December 2019

This paper analyzes pearson residuals, which is an important element of chi-square test statistic, in a contingency table from the viewpoint of matrix theory as follows. First, a given contingency table is viewed as a matrix and the residual of each element in a matrix are obtained as the difference bewteen observed values and expected values calculated by marginal distributions. Then, each residual σ _{ij} is decomposed into the linear sum of the 2 × 2 subderminants of a original matrix, except for i-th column and j-th row. Furthermore, the number of the determinants is equal to the degree of freedom for the chi-square test statistic for a given contingency table. Thus, 2 × 2 subdeterminants in a contingencymatrix determine the degree of statistical independence of two attributes as elementary granules.
Object segmentation in video via graph cut built on	superpixels
Authors: Kwolek Bogdan
Published: December 2019

This paper proposes a real-time scheme for object segmentation in video. In the first stage a segmentation based on pairwise region comparison is utilized to oversegment image through extracting superpixels. Next, the algorithmapplies the graph cut built on such superpixels, instead of the image pixels. Owing to the optimization is performed on a simpler graph and in consequence the object segmentation runs in shorter time. Tracking of object features over time contributes toward improved segmenting the object from one image to another. The segmentation information supports following the entire object, instead of just a few features on it. The objects are segmented correctly as complete entities, despite the high variability of the object shape and cluttered background. Experimental results illustrate the efficiency and effectiveness of the algorithm.
A Fast VQ Codebook Generation Algorithm Based on Otsu Histogram	Threshold
Authors: Huang Chang-Chin , Tsai Du-Shiau , Horng Gwoboa
Published: December 2019

In vector quantization, the codebook generation problem can be formulated as a classification problem of dividing N $_{p}$ training vectors into N $_{c}$ clusters, where N $_{p}$ is the training size of input vectors and N $_{c}$ is the codeword size of codebook. For large N $_{p}$ and N $_{c}$ , a traditional search algorithmsuch as the LBG method can hardly find the global optimal classification and needs a great deal of calculation. In this paper, a novel VQ codebook generation method based on Otsu histogram threshold is proposed. The computational complexity of squared Euclidean distance can be reduced to O(N $_{p}$ log $_{2}$ N $_{c}$ ) for a codebook with gray levels. Our method provides better image quality than recent proposed schemes in high compression ratio. The experimental results and the comparisons show that this method can not only reduce the computational complexity of squared Euclidean distance but also find better codewords to improve the quality of the resulted VQ codebook.
An Information-Hiding Scheme Based on Quantization-Based Embedding	Technique
Authors: Lu Tzu-Chuen , Chang Chin-Chen , Liu Yi-Long
Published: December 2019

Information hiding is a technique that embeds secret data in digital media for using in a variety of applications, including ownership protection, authentication, access control, annotation and so on. In this paper, we propose an information hiding scheme based on quantization-based embedding technique to conceal information in gray-scale image. The proposed scheme was tested with a variety of gray images. According to the experimental results, hidden information can be extracted correctly and quickly from the stego image. In addition, the stego image has only a little distortion compared with the cover image. The proposed scheme can not only hide a large amount of information in the cover image, but can also repair the stego image such that the repaired image is almost the same as the cover image.
Undecidability Results for Timed Automata with Silent	Transitions
Authors: Bouyer Patricia , Haddad Serge , Reynier Pierre-Alain
Published: December 2019

In this work, we study decision problems related to timed automata with silent transitions (TA $_{ϵ}$ ) which strictly extend the expressiveness of timed automata (TA). We first answer negatively a central question raised by the introduction of silent transitions: can we decide whether the language recognized by a TA $_{ϵ}$ can be recognized by some TA? Then we establish in the framework of TA $_{ϵ}$ some old open conjectures that O. Finkel has recently solved for TA. His proofs follow a generic scheme which relies on the fact that only a finite number of configurations can be reached by a TA while reading a timed word. This property does not hold for TA $_{ϵ}$ , the proofs in the framework of TA $_{ϵ}$ thus require more elaborated arguments. We establish undecidability of complementability, minimization of the number of clocks, and closure under shuffle. We also show these results in the framework of infinite timed languages.
Evolutionary Approach to Data Discretization for Rough Sets	Theory
Authors: Czerniak Jacek
Published: December 2019

This article presents the LDGen method which is based on genetic algorithm. The author proposed evolutionary approach to the solution of the discretization problem for systems that induce rules on the basis of rough sets theory. The study describes details of the method with special focus on the crossing operator. The proposed approach concerns working with multidimensional samples. Thanks to application of the author's own method of for visualizing multidimensionality, i.e. so called Pipes of Samples, it was possible to visualize up to 360 dimensions, which is usually sufficient in case of problems the Rough Sets Theory deals with. Mutation and crossing methods were developed using this visualisation so that, for real numbers, it allowed to create individuals that describe one solution of the discretization. Hence the population is a set of many complete discretizations of all the attributes.
Bisimulation Minimisation of Weighted Automata on Unranked Trees
Authors: Högberg Johanna , Maletti Andreas , Vogler Heiko
Published: December 2019

Several models of automata are available that operate unranked trees. Two well-known examples are the stepwise unranked tree automaton (suta) and the parallel unranked tree automaton (puta). By adding a weight, taken from some semiring, to every transition we generalise these two qualitative automata models to quantitative models, thereby obtaining weighted stepwise unranked tree automata (wsuta) and weighted parallel unranked tree automata (wputa); the qualitative automata models are reobtained by choosing the BOOLEAN semiring. The weighted versions have applications in natural language processing, XML-based data management and quantitative information retrieval. We address the minimisation problem of wsuta and wputa by using (forward and backward) bisimulations and we prove the following results: (1) for every wsuta an equivalent forward (resp. backward) bisimulation minimal wsuta can be computed in time O(mn) where n is the number of states and m is the number of transitions of the given wsuta; (2) the same result is proved for wputa instead of wsuta; (3) if the semiring is additive cancellative or the BOOLEAN semiring, then the bound can be improved to O(mlog n) for both wsuta and wputa; (4) for every deterministic puta we can compute a minimal equivalent deterministic puta in time O(mlog n); (5) the automata models wsuta, wputa, and weighted unranked tree automaton have the same computational power.
Complexity of Normal Form Properties and Reductions for Term	Rewriting Problems Complexity of Normal Form Properties and Reductions for Term	Rewriting Problems
Authors: Verma Rakesh
Published: December 2019

We present several new and some significantly improved polynomial-time reductions between basic decision problems of term rewriting systems. We prove two theorems that imply tighter upper bounds for deciding the uniqueness of normal forms (UN $^{=}$ ) and unique normalization (UN $^{→}$ ) properties under certain conditions. From these theorems we derive a new and simpler polynomial-time algorithm for the UN $^{=}$ property of ground rewrite systems, and explicit upper bounds for both UN $^{=}$ and UN $^{→}$ properties of left-linear right-ground systems. We also show that both properties are undecidable for right-ground systems. It was already known that these properties are undecidable for linear systems. Hence, in a sense the decidability results are "close" to optimal.
Towards a Formal Semantics for the Process Model of the Taverna	Workbench. Part I
Authors: Sroka Jacek , Hidders Jan
Published: December 2019

Workflow development and enactment workbenches are becoming a standard tool for conducting in silico experiments. Their main advantages are easy to operate user interfaces, specialized and expressive graphical workflow specification languages and integration with a huge number of bioinformatic services. A popular example of such a workbench is Taverna, which has many additional useful features like service discovery, storing intermediate results and tracking data provenance.

We discuss a detailed formal semantics for Scufl - the workflow definition language of the Taverna workbench. It has several interesting features that are notmet in other models including dynamic and transparent type coercion and implicit iteration, control edges, failure mechanisms, and incominglinks strategies. We study these features and investigate their usefulness separately as well as in combination, and discuss alternatives.

The formal definition of such a detailed semantics not only allows to exactly understand what is being done in a given experiment, but is also the first step toward automatic correctness verification and allows the creation of auxiliary tools that would detect potential errors and suggest possible solutions to workflow creators, the same way as Integrated Development Environments aid modern programmers. A formal semantics is also essential for work on enactment optimization and in designing the means to effectively query workflow repositories.

This paper is the first of two. It defines, explains and discusses fundamental notions for describing Scufl graphs and their semantics. Then, in the second part, we use these notions to define the semantics and show that our definition can be used to prove properties of Scufl graphs.
A Proof of Plotkin's Conjecture
Authors: Yinbin Lei , Maokang Luo
Published: December 2019

In 1978, G. Plotkin [7] conjectured that for the three-element truthvalue dcpo T, if κ > ω then the function space [T $^{κ}$ → T $^{κ}$ ] is not a retract of T $^{κ}$ . In this short paper, we constructively prove a stronger result that if κ > ω then the function space [T $^{κ}$ → T $^{κ}$ ] is not a retract of the Cartesian product of any family of finite posets. Thus Plotkin's Conjecture is proved to be correct.
On the Parallelization of Self-Adaptive hp-Finite Element Methods	Part I. Composite Programmable Graph GrammarModel
Authors: Paszyński Maciej
Published: December 2019

The paper present the composite programmable (CP) graph grammar model of the selfadaptive hp Finite Element Method (hp-FEM) algorithm. The model incorporates the process of the initial mesh generation, direct solver execution, as well as mesh transformations resulting from selectedoptimal hp refinements. The computational mesh is represented by the CP-graph. The operations performed over the mesh are expressed by the graph grammar productions. The graph grammar model allows for the definition of the computational tasks for the Partitioning, Communication, Agglomeration and Mapping (PCAM) method of the parallelization of the self-adaptive hp-FEM algorithm.
On the Parallelization of Self-Adaptive hp-Finite Element Methods	Part II. Partitioning Communication Agglomeration Mapping (PCAM) Analysis
Authors: Paszyński Maciej
Published: December 2019

The paper presents a general methodology for an efficient parallelization of the fully automatic hp-adaptive Finite Element Method (hp-FEM). The self-adaptive hp-FEM algorithm expressed in terms of the graph grammar productions is analyzed by utilizing the Partitioning Communication Agglomeration Mapping (PCAM) model. The computational tasks are defined over a graph model of the computational mesh. It is done for all parts of the algorithm: the generation of an initial mesh, direct solver (including the integration and elimination of degrees of freedom), mesh transformations (including the h and p refinements), as well as the selection of the optimal refinements. The computation and communication complexities of the resulting parallel algorithms are analyzed. The paper is concluded with the sequence of massive parallel computations. From the performed tests it implies that the code scales well up to 200 processors.
The Injectivity of the Global Function of a Cellular Automaton in	the Hyperbolic Plane is Undecidable
Authors: Margenstern Maurice
Published: December 2019

In this paper, we look at the following question. We consider cellular automata in the hyperbolic plane, see [6, 22, 9, 12] and we consider the global function defined on all possible configurations. Is the injectivity of this function undecidable? The problem was answered positively in the case of the Euclidean plane by Jarkko Kari, in 1994, see [4]. In the present paper, we show that the answer is also positive for the hyperbolic plane: the problem is undecidable.
Avoiding Irreducible CSC Conflicts by Internal Communication
Authors: Wist Dominic , Wollowski Ralf , Schaefer Mark , Vogler Walter
Published: December 2019

Resynthesis of handshake specifications obtained e.g. from BALSA or TANGRAM with speed-independent logic synthesis from STGs is a promising approach. To deal with state-space explosion,we suggested STG decomposition; a problemis that decomposition can lead to irreducible CSC conflicts.

Here, we present a new approach to solve such conflicts by introducing internal communication between the components. We give some first, very encouraging results for very large STGs concerning synthesis time and circuit area.
Dynamic Error Handling in Service Oriented Applications
Authors: Guidi Claudio , Lanese Ivan , Montesi Fabrizio , Zavattaro Gianluigi
Published: December 2019

Service Oriented Computing (SOC) allows for the composition of services which communicate using unidirectional one-way or bidirectional request-response communication patterns. Most service orchestration languages proposed so far provide also primitives for error handling based on fault, termination, and compensation handlers. Our work is motivated by the difficulties encountered in programming some error handling strategies using current error handling primitives. We propose as a solution an orchestration programming style in which handlers are dynamically installed. We assess our proposal by formalizing our approach as an extension of the process calculus SOCK and by proving that our formalization satisfies some expected high-level properties.
A Recursive Classifier System for Partially Observable	Environments
Authors: Hamzeh Ali , Hashemi Sattar , Sami Ashkan , Rahmani Adel
Published: December 2019

Previously we introduced Parallel Specialized XCS (PSXCS), a distributed-architecture classifier system that detects aliased environmental states and assigns their handling to created subordinate XCS classifier systems. PSXCS uses a history-window approach, but with novel efficiency since the subordinateXCSs, which employ the windows, are only spawned for parts of the state space that are actually aliased. However, because the window lengths are finite and set manually, PSXCS may fail to be optimal in difficult test mazes. This paper introduces Recursive PSXCS (RPSXCS) that automatically spawns windows wherever more history is required. Experimental results show that RPSXCS is both more powerful and learns faster than PSXCS. The present research suggests new potential for history approaches to partially observable environments.
An Effective Message Embedding Scheme for 3D Models
Authors: Li Meng-Tsan , Huang Nien-Ching , Wu Kuo-Chen , Jan Chin-Kai , Wang Chung-Ming
Published: December 2019

We present an effective message embedding scheme for 3D models. We propose the unit length as the quantizer to generate an embedding order list and an embedding index list. Our scheme considers every two elements in the embedding order list as the order pair, and we embed 3 bits of 0 or 1 secret message into the index pair associated with the order pair. The message embedding is effective requiring, at most, adding 1 to, or subtracting 1 from, the index pair. This reflects a slight perturbation of a points coordinates where the magnitude of the perturbation is no greater than one unit length. Our algorithm achieves a high embedding capacity, being 4.5 times the number of points in the point cloud models. This amount of capacity allows us to convey a 502x502 resolution of the black-and-white image into a point cloud model consisting of 56,194 points for covert communication. The capacity magnitude is 50%-75% higher than that of the current state-ofthe- art algorithms, yet the model distortion due to the message embedding is smaller than that of our counterparts. Our algorithm is robust against translation, rotation, and uniformly scaling operations. It is fast, simple to implement, and the message can be extracted without referring to the original point cloud model. We believe our scheme is appropriate for most point cloud models.
Complex Algebras of Arithmetic
Authors: Düntsch Ivo , Pratt-Hartmann Ian
Published: December 2019

An arithmetic circuit is a labeled, acyclic directed graph specifying a sequence of arithmetic and logical operations to be performed on sets of natural numbers. Arithmetic circuits can also be viewed as the elements of the smallest subalgebra of the complex algebra of the semiring of natural numbers. In the present paper we investigate the algebraic structure of complex algebras of natural numbers and make some observations regarding the complexity of various theories of such algebras.
On the Insecurity of an Identity Based Proxy Re-encryption Scheme
Authors: Wang Xu An , Yang Xiaoyuan
Published: December 2019

At Pairing'07, Matsuo proposed two proxy re-encryption schemes: proxy re-encryption fromCBE to IBE and IBE to IBE. Now both schemes have been standardized by P1363.3workgroup. In this paper, we show that their identity based proxy re-encryption scheme is insecure. We give two attacks to this scheme. The first attack shows that the proxy can re-encrypt any IBE user's ciphertext to be the delegatee's ciphertext. The second attack implies that, if the proxy colludes with any delegatee, the proxy and this delegatee can derive any other IBE user's secret key.
Free-Choice Petri Nets without Frozen Tokens, and Bipolar	Synchronization Systems
Authors: Wehler Joachim
Published: December 2019

Bipolar synchronization systems (BP-systems) constitute a class of coloured Petri nets, well suited for modelling the control flow of discrete dynamical systems. Every BP-system has an underlying ordinary Petri net, a T-system. It further has a second ordinary net attached, a free-choice system. We prove that a BP-system is safe and live if the T-system and the free-choice system are safe and live and the free-choice system in addition has no frozen tokens. This result is the converse of a theorem of Genrich and Thiagarajan and proves an old conjecture. As a consequence we obtain two results about the existence of safe and live BP-systems with prescribed ordinary Petri nets. For the proof of these theorems we introduce the concept of a morphism between Petri nets as a means of comparing different Petri nets. We then apply the classical theory of free-choice systems.
A Most General Edge Elimination Polynomial – Thickening of Edges
Authors: Hoffmann Christian
Published: December 2019

We consider a graph polynomial ξ (G; x, y, z) introduced by Ilia Averbouch,BennyGodlin, and Johann A.Makowsky (2008). This graph polynomial simultaneously generalizes the Tutte polynomial as well as a bivariate chromatic polynomial defined by Klaus Dohmen, André Pönitz, and Peter Tittmann (2003). We derive an identity which relates the graph polynomial ξ of a thickened graph (i.e. a graph with each edge replaced by k copies of it) to ξ of the original graph. As a consequence, we observe that at every point (x, y, z), except for points lying within some set of dimension 2, evaluating ξ is #P-hard. Thus, ξ supports Johann A. Makowsky's difficult point conjecture for graph polynomials (2008).
A Note on Two-pebble Automata Over Infinite Alphabets
Authors: Kaminski Michael , Tan Tony
Published: December 2019

It is shown that the emptiness problemfor two-pebble automata languages is undecidable and that two-pebble automata are weaker than three-pebble automata.
Evolutionary Rough Parallel Multi-Objective Optimization Algorithm
Authors: Maulik Ujjwal , Sarkar Anasua
Published: December 2019

A hybrid unsupervised learning algorithm, which is termed as Parallel Rough-based Archived Multi-Objective Simulated Annealing (PARAMOSA), is proposed in this article. It comprises a judicious integration of the principles of the rough sets theory and the scalable distributed paradigm with the archived multi-objective simulated annealing approach. While the concept of boundary approximations of rough sets in this implementation, deals with the incompleteness in the dynamic classification method with the quality of classification coefficient as the classificatory competencemeasurement, the time-efficient parallel approach enables faster convergence of the Pareto-archived evolution strategy. It incorporates both the rough set-based dynamic archive classifi- cation method and the distributed implementation as a two-phase speedup strategy in this algorithm. A measure of the amount of domination between two solutions has been incorporated in this work to determine the acceptance probability of a new solution with an improvement in the spread of the non-dominated solutions in the Pareto-front by adopting rough sets theory. A complexity analysis of the proposed algorithm is provided. An extensive comparative study of the proposed algorithm with three other existing and well-known Multi-Objective Evolutionary Algorithms (MOEAs) demonstrate the effectiveness of the former with respect to four existing performance metrics and eleven benchmark test problems of varying degrees of difficulties. The superiority of this new parallel implementation over other algorithms also has been demonstrated in timing, which achieves a near optimal speedup with a minimal communication overhead.
Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes
Authors: Aratsu Taku , Hirata Kouichi , Kuboyama Tetsuji
Published: December 2019

This article proposes an approximation of the tree edit distance through the string edit distance for binary tree codes, instead of for Euler strings introduced by Akutsu (2006). Here, a binary tree code is a string obtained by traversing a binary tree representation with two kinds of dummy nodes of a tree in preorder. Then, we show that σ/2 ≤ τ ≤ (h + 1)σ + h, where τ is the tree edit distance between trees, and σ is the string edit distance between their binary tree codes and h is the minimum height of the trees.
Computing Maximal Error-detecting Capabilities and Distances of Regular Languages
Authors: Konstantinidis Stavros , Silva Pedro V.
Published: December 2019

A (combinatorial) channel consists of pairs of words representing all possible input-output channel situations. In a past paper, we formalized the intuitive concept of “largest amount of errors” detectable by a given language L, by defining the maximal error-detecting capabilities of L with respect to a given class of channels, and we showed how to compute all maximal error-detecting capabilities (channels) of a given regular language with respect to the class of rational channels and a class of channels involving only the substitution-error type. In this paper we resolve the problem for channels involving any combination of the basic error types: substitution, insertion, deletion. Moreover, we consider the problem of finding the inverses of these channels, in view of the fact that L is error-detecting for γ if and only if it is error-detecting for the inverse of γ. We also discuss a natural method of reducing the problem of computing (inner) distances of a given regular language L to the problem of computing maximal error-detecting capabilities of L.
Another Constructed Chaotic Image Encryption Scheme Based on Toeplitz Matrix and Hankel Matrix
Authors: Ye Guodong
Published: December 2019

This paper presents a novel image encryption scheme based on Toeplitz matrix and Hankel matrix. According to the definition and the expression of Toeplitz matrix and Hankel matrix, we permutate the positions of image pixels to confuse the relationship between the plain-image and cipher-image, and construct a new key. To enhance security further, hyper-chaos system of Lü and Chen is taken to change the grey distribution of image pixels simultaneously. Numerical experimental results demonstrate that the key space is large enough, and the key is sensitive to initial conditions to resist the brute-force attack in the proposed scheme. Additionally, the distribution of grey values in encrypted image has a random-like behavior to resist statistical analysis. The proposed encryption scheme in this paper can suggest a high secure and efficient way for real-time image encryption and transmission in practice.
Some Remarks on Testing Irreducibility of Polynomials and Normality of Bases in Finite Fields
Authors: Gashkov Sergej B. , Gashkov Igor B.
Published: December 2019

We prove some improvements for well-known upper bound of complexity of testing irreducibility of polynomials over finite fields. Also the fast modification of well-known probabilistic algorithm finding a normal bases in special finite fields is presented.
Modeling Contexts with Dependent Types
Authors: Dapoigny Richard , Barlatier Patrick
Published: December 2019

In the area of knowledge representation, a challenging topic is the formalization of context knowledge on the basis of logical foundations and ontological semantics. However, most attempts to provide a formal model of contexts suffer from a number of difficulties, such as limited expressiveness of representation, restricted variable quantification, lack of (meta) reasoning about properties, etc. In addition, type theory originally developed for formal modeling of mathematics has also been successfully applied to the correct specification of programs and in the semantics of natural language. In this paper, we suggest a type theoretical approach to the problem of context and action modeling. Type theory is used both for representing the system's knowledge of the discourse domain and for reasoning about it. For that purpose, we extend an existing dependent type theory having nice properties, with context-based rules and appropriate inductive types. We claim that the resulting theory exploiting the power of dependent types is able to provide a very expressive system together with a unified theory allowing higher-order reasoning.
On the Use of Naive Bayesian Classifiers for Detecting Elementary and Coordinated Attacks
Authors: Kenaza Tayeb , Tabia Karim , Benferhat Salem
Published: December 2019

Bayesian networks are very powerful tools for knowledge representation and reasoning under uncertainty. This paper shows the applicability of naive Bayesian classifiers to two major problems in intrusion detection: the detection of elementary attacks and the detection of coordinated ones. We propose two models starting with stating the problems and defining the variables necessary for model building using naive Bayesian networks. In addition to the fact that the construction of such models is simple and efficient, the performance of naive Bayesian networks on a representative data is competing with the most efficient state of the art classification tools. We show how the decision rules used in naive Bayesian classifiers can be improved to detect new attacks and new anomalous activities. We experimentally show the effectiveness of these improvements on a recent Web-based traffic. Finally, we propose a naive Bayesian network-based approach especially designed to detect coordinated attacks and provide experimental results showing the effectiveness of this approach.
Formal Analysis of SystemC Designs in Process Algebra
Authors: Hojjat Hossein , Mousavi Mohammad Reza , Sirjani Marjan
Published: December 2019

SystemC is an IEEE standard system-level language used in hardware/software co-design and has been widely adopted in the industry. This paper describes a formal approach to verifying SystemC designs by providing a mapping to the process algebra mCRL2. Our mapping formalizes both the simulation semantics as well as exhaustive state-space exploration of SystemC designs. By exploiting the existing reduction techniques of mCRL2 and also its model-checking tools, we efficiently locate the race conditions in a system and resolve them. A tool is implemented to automatically perform the proposed mapping. This mapping and the implemented tool enabled us to exploit process-algebraic verification techniques to analyze a number of case-studies, including the formal analysis of a single-cycle and a pipelined MIPS processor specified in SystemC.
Mechanical Analysis of Finite Idempotent Relations
Authors: Kammüller Florian
Published: December 2019

We use the technique of interactive theorem proving to develop the theory and an enumeration technique for finite idempotent relations. Starting from a short mathematical characterization of finite idempotents defined and proved in Isabelle/HOL, we derive first an iterative procedure to generate all instances of idempotents over a finite set. From there, we develop a more precise theoretical characterization giving rise to an efficient predicate that can be executed in the programming language ML. Idempotent relations represent a very basic, general mathematical concept but the steps taken to develop their theory with the help of Isabelle/HOL are representative for developing algorithms from a mathematical specification.
Trade-Offs Between Time, Space, Cooperation, and Communication Complexity for CD Grammar Systems
Authors: Cojocaru Liliana
Published: December 2019

In this paper we investigate the communication and cooperation phenomenon in Cooperating Distributed Grammar Systems (henceforth CDGSs). In this respect, we define several complexity structures and two complexity measures, the cooperation and communication complexity measures. These measures are studied with respect to the derivation modes and fairness conditions under which CDGSs may work. We deal with trade-offs between time, space, cooperation, and communication complexity of languages generated by CDGSs with regular, linear, and context-free components. Cooperation and communication processes in CDGSs with regular and linear components are of equal complexity. The two (equal) cooperation and communication complexity measures are either constant or linear, as functions of lengths of words in the generated language. The same result holds for the cooperation and communication complexity of q-fair languages generated by CDGSs with regular and linear components. For the case of non-constant communication (cooperation) the time and space used by a nondeterministic multitape Turing machine to recognize weakly q-fair languages are linear, as is the communication (cooperation) complexity. For CDGSs with context-free components the cooperation and communication complexity may be different. These measures are either linear or logarithmic functions, in terms of lengths of words in the generated language. In order to find trade-offs between time, space, cooperation, and communication complexity of languages generated by CDGSs with context-free components we study asymptotic behavior of growth functions characteristic to these measures. We prove that languages generated by CDGSs with context-free components are accepted by nondeterministic multitape Turing machines either in quadratic time, linear space, and with cooperation complexity that varies from logarithmic to linear, or in polynomial or exponential time and space, and linear cooperation complexity.
Look-back Techniques for ASP Programs with Aggregates
Authors: Faber Wolfgang , Leone Nicola , Maratea Marco , Ricca Francesco
Published: December 2019

The introduction of aggregates has been one of the most relevant language extensions to Answer Set Programming (ASP). Aggregates are very expressive, they allow to represent many problems in a more succinct and elegant way compared to aggregate-free programs. A significant amount of research work has been devoted to aggregates in the ASP community in the last years, and relevant research results on ASP with aggregates have been published, on both theoretical and practical sides. The high expressiveness of aggregates (eliminating aggregates often causes a quadratic blow-up in program size) requires suitable evaluation methods and optimization techniques for an efficient implementation. Nevertheless, in spite of the above-mentioned research developments, aggregates are treated in a quite straightforward way in most ASP systems. In this paper, we explore the exploitation of look-back techniques for an efficient implementation of aggregates. We define a reason calculus for backjumping in ASP programs with aggregates. Furthermore, we describe how these reasons can be used in order to guide look-back heuristics for programs with aggregates. We have implemented both the new reason calculus and the proposed heuristics in the DLV system, and have carried out an experimental analysis on publicly available benchmarks which shows significant performance benefits.
Analysis of Markov Boundary Induction in Bayesian Networks: A New View From Matroid Theory
Authors: Feng Dingcheng , Chen Feng , Xu Wenli
Published: December 2019

Learning Markov boundaries from data without having to learn a Bayesian network first can be viewed as a feature subset selection problem and has received much attention due to its significance in the wide applications of AI techniques. Popular constraint based methods suffer from high computational complexity and are usually unstable in spaces of high dimensionality. We propose a new perspective from matroid theory towards the discovery of Markov boundaries of random variable in the domain, and develop a learning algorithm which guarantees to recover the true Markov boundaries by a greedy learning algorithm. Then we use the precision matrix of the original distribution as a measure of independence to make our algorithm feasible in large scale problems, which is essentially an approximation of the probabilistic relations with Gaussians and can find possible variables in Markov boundaries with low computational complexity. Experimental results on standard Bayesian networks show that our analysis and approximation can efficiently and accurately identify Markov boundaries in complex networks from data.
On the State Complexity of Star of Union and Star of Intersection
Authors: Jirásková Galina , Okhotin Alexander
Published: December 2019

The state complexity of the star of union of an m-state DFA language and an n-state DFA language is proved to be 2m+n−1−2m−1−2n−1+1 for every alphabet of at least two letters. The state complexity of the star of intersection is established as 3/4 2mn for every alphabet of six or more letters. This improves the recent results of A. Salomaa, K. Salomaa and Yu (“State complexity of combined operations”, Theoret. Comput. Sci., 383 (2007) 140–152).