bluuebunny/crossref_metadata_2025 huggingface dataset:
Stochastic Populations, Power Law and Fitness Aggregation in Genetic Algorithms
Authors: Ma Zhanshan Sam
Published: December 2019

Natural populations are dynamic in both time and space. In biological populations such as insects, spatial distribution patterns are often studied as the first step to characterize population dynamics. In nature, the spatial distribution patterns of insect populations are considered as the emergent expression (property) of individual behaviors at population levels and are fine-tuned or optimized by natural selection. This inspiration prompts us to investigate the possibly similar mechanisms in Genetic Algorithms (GA) populations. In this study, we introduce the mathematical models for the spatial distribution patterns of insect populations to GA with the conjecture that the emulation of biological populations in nature may lead to computational improvement. In particular, we introduce three modeling approaches from the research of spatial distribution patterns of insect populations: (i) probability distribution modeling approach, (ii) aggregation index approach, and (iii) Taylor's (1961, 1977) Power Law, Iwao's (1968, 1976) Mean Crowding Model and Ma's (1991c) population aggregation critical density (PACD), to characterize populations in GA. With these three approaches, we investigate four mappings from the research field of insect spatial distribution patterns to GA populations in order to search for possible counterpart mechanisms or features in GA. They are: (i) mapping insect spatial distribution patterns to GA populations or allowing GA populations to be controlled by stochastic distribution models that describe insect spatial distributions; (ii) mapping insect population distribution to GA population fitness distribution via Power Law and PACD modeling; (iii) mapping population aggregation dynamics to GA fitness progression across generations (or fitness aggregation dynamics in GA) via insect population aggregation index; (iv) mapping insect population sampling model to optimal GA population sizing. With regard to the mapping (i), the experiment results show the significant improvements in GA computational efficiency in terms of the reduced fitness evaluations and associated costs. This prompts us to suggest using probability distribution models, or what we call stochastic GA populations, to replace the fixed-size population settings. We also found the counterpart for the second mapping, the wide applicability of Power Law and Mean Crowding model to the fitness distribution in GA populations. The testing of the third and fourth mappings is very preliminary; we use example cases to suggest two further research problems: the potential to use fitness aggregation dynamics for controlling the number of generations iterated in GA searches, and the possibility to use fitness aggregation distribution parameters [(obtained in mapping (ii)] in determining the optimum population size in GA. A third interesting research problem is to investigate the relationship between mapping (i) and (iii), i.e., the controlling of both population sizes and population generations.
Filtrations of Formal Languages by Arithmetic Progressions
Authors: Mousavi Hamoon , Shallit Jeffrey
Published: December 2019

A filtration of a formal language L by a sequence s maps L to the set of words formed by taking the letters of words of L indexed only by s. We consider the languages resulting from filtering by all arithmetic progressions. If L is regular, it is easy to see that only finitely many distinct languages result; we give bounds on the number of distinct languages in terms of the state complexity of L. By contrast, there exist CFL's that give infinitely many distinct languages as a result. We use our technique to show that two related operations, including diag (which extracts the diagonal of words of square length arranged in a square array), preserve regularity but do not preserve context-freeness.
CHIRA—Convex Hull Based Iterative Algorithm of Rules Aggregation
Authors: Sikora Marek , Gudyś Adam
Published: December 2019

In the paper we present CHIRA, an algorithm performing decision rules aggregation. New elementary conditions, which are linear combinations of attributes may appear in rule premises during the aggregation, leading to so-called oblique rules. The algorithm merges rules iteratively, in pairs, according to a certain order specified in advance. It applies the procedure of determining convex hulls for regions in a feature space which are covered by aggregated rules. CHIRA can be treated as the generalization of rule shortening and joining algorithms which, unlike them, allows a rule representation language to be changed. Application of presented algorithm allows one to decrease a number of rules, especially in the case of data in which decision classes are separated by hyperplanes not perpendicular to the attribute axes. Efficiency of CHIRA has been verified on rules obtained by two known rule induction algorithms, RIPPER and q-ModLEM, run on 18 benchmark data sets. Additionally, the algorithm has been applied on synthetic data as well as on a real-life set concerning classification of natural hazards in hard-coal mines.
Redefinition of Decision Rules Based on the Importance of Elementary Conditions Evaluation
Authors: Sikora Marek
Published: December 2019

The paper presents an algorithm of decision rules redefinition that is based on evaluation of the importance of elementary conditions occurring in induced rules. Standard and simplified (heuristic) indices of elementary condition importance evaluation are described. There is a comparison of the results obtained by both indices concerning classifiers quality and elementary condition rankings estimated by the indices. The efficiency of the proposed algorithm has been verified on 21 benchmark data sets. Moreover, an analysis of practical applications of the proposed methods for biomedical and medical data analysis is presented. The obtained results show that the redefinition reduces considerably a rule set needed to describe each decision class. Additionally, after the rule set redefinition negated elementary conditions may also occur in new rules.
Fuzzy and Intuitionistic Fuzzy Turing Machines
Authors: Moniri Morteza
Published: December 2019

First we define a new class of fuzzy Turing machines that we call Generalized Fuzzy Turing Machines. Our machines are equipped with rejecting states as well as accepting states. While we use a t-norm for computing degrees of accepting or rejecting paths, we use its dual t-conorm for computing the accepting or rejecting degrees of inputs. We naturally define when a generalized fuzzy Turing machine accepts or decides a fuzzy language. We prove that a fuzzy language L is decidable if and only if L and its complement are acceptable. Moreover, to each r.e. or co-r.e language L, we naturally correspond a fuzzy language which is acceptable by a generalized fuzzy Turing machine. A converse to this result is also proved. We also consider Atanasov's intuitionistic fuzzy languages and introduce a version of fuzzy Turing machine for studying their computability theoretic properties.
On the Computational Complexity of Bongartz's Algorithm
Authors: Mróz Andrzej
Published: December 2019

We study the complexity of Bongartz's algorithm for determining a maximal common direct summand of a pair of modules M, N over k-algebra Λ; in particular, we estimate its pessimistic computational complexity 𝒪(rm6n2(n + m log n)), where m = dimkM ≤ n = dimkN and r is a number of common indecomposable direct summands of M and N. We improve the algorithm to another one of complexity 𝒪(rm4n2(n+m log m)) and we show that it applies to the isomorphism problem (having at least an exponential complexity in a direct approach). Moreover, we discuss a performance of both algorithms in practice and show that the “average” complexity is much lower, especially for the improved one (which becomes a part of QPA package for GAP computer algebra system).
Clustering with Missing Values
Authors: Simiński Krzysztof
Published: December 2019

The paper presents the clustering algorithm for data with missing values. In this approach both marginalisation and imputation are applied. The result of the clustering is the type-2 fuzzy set / rough fuzzy set. This approach enables the distinction between original and imputed data. The method can be applied to the data sets with all attributes lacking some values. The paper is accompanied by the numerical examples of clustering of synthetic and real-life data sets.
Relational Operations and Uncertainty Measure in Rough Relational Database
Authors: Jiang Feng , Wan Xiaoyan , Sui Yuefei , Cao Cungen , Du Junwei
Published: December 2019

The traditional relational database model (RDM) is not effective for dealing with imprecise and uncertain data as it deals with precise and unambiguous data. Hence, Beaubouef et al. proposed the rough relational database model (RRDM) for the management of uncertainty in relational databases. Beaubouef et al. defined the corresponding rough relational operators in rough relational databases as in ordinary relational databases. And to give an effective measure of uncertainty in rough relational databases, they defined the rough relation entropy. In this paper, we further discuss the issues of relational operations and uncertainty measure in rough relational databases. We give some new definitions for rough relational operators and rough relation entropy in rough relational databases. Furthermore, we discuss the basic properties of rough relational operators and rough relation entropy, as well as the connections between rough relational operators and rough relation entropy.
Araucaria Trees: Construction and Grafting Theorems
Authors: Schmitt Dominique , Spehner Jean-Claude
Published: December 2019

Araucarias have been introduced by Schott and Spehner as trees which appear in the minimal automaton of the shuffle of words. We give here a new definition of araucarias which is more constructive and we prove that our definition of araucarias is equivalent to the original one. From the new definition we derive an optimal algorithm for the construction of araucarias and a new method for calculating their size. Moreover we characterize araucarias by properties of their maximal paths, by associating a capacity to every edge. We then show that every araucaria can be obtained by grafting and merging smaller araucarias. We prove also that every directed tree can be embedded in an araucaria. Moreover we define a capacity for every vertex of an araucaria, which leads to different new enumeration formulas for araucarias.
Complete Conceptual Schema Algebras
Authors: Ma Hui , Noack René , Schewe Klaus-Dieter , Thalheim Bernhard , Wang Qing
Published: December 2019

A schema algebra comprises operations on database schemata for a given data model. Such algebras are useful in database design as well as in schema integration. In this article we address the necessary theoretical underpinnings by introducing a novel notion of conceptual schema morphism that captures at the same time the conceptual schema and its semantics by means of the set of valid instances. This leads to a category of schemata that is finitely complete and co-complete. This is the basis for a notion of completeness of schema algebras, if it captures all universal constructions in the category of schemata. We exemplify this notion of completeness for a recently introduced particular schema algebra.
Residual Closeness in Cycles and Related Networks
Authors: Odabaş Zeynep Nihan , Aytaç Aysun
Published: December 2019

Networks are known to be prone to node or link failures. A central issue in the analysis of networks is the assessment of their stability and reliability. The main aim is to understand, predict, and possibly even control the behavior of a networked system under attacks or disfunctions of any type. A central concept that is used to assess stability and robustness of the performance of a network under failures is that of vulnerability. A network is usually represented by an undirected simple graph where vertices represent processors and edges represent links between processors. Different approaches to properly define a measure for graph vulnerability has been proposed so far. In this paper, we study the vulnerability of cycles and related graphs to the failure of individual vertices, using a measure called residual closeness which provides a more sensitive characterization of the graph than some other well-known vulnerability measures.
On Language Equations with One-sided Concatenation
Authors: Baader Franz , Okhotin Alexander
Published: December 2019

Language equations are equations where both the constants occurring in the equations and the solutions are formal languages. They have first been introduced in formal language theory, but are now also considered in other areas of computer science. In the present paper, we restrict the attention to language equations with one-sided concatenation, but in contrast to previous work on these equations, we allow not just union but all Boolean operations to be used when formulating them. In addition, we are not just interested in deciding solvability of such equations, but also in deciding other properties of the set of solutions, like its cardinality (finite, infinite, uncountable) and whether it contains least/greatest solutions. We show that all these decision problems are EXPTIME-complete.
Decomposition of Relations and Concept Lattices
Authors: Berghammer Rudolf , Winter Michael
Published: December 2019

We introduce the decomposition of an arbitrary relation into a sequential composition of three relations, viz. of a mapping with a partial order and then the transpose of a mapping. After presenting some basic properties, we investigate the specific classes of junkfree, irreducible and minimal decompositions and show that for all relations a minimal decomposition exists. We also study decompositions with regard to DedekindMacNeille completions and concept lattices. These constructions are closely related to decompositions of relations. In our setting the fundamental theorem of concept lattices states that concept lattices are minimal-complete decompositions and all such decompositions are isomorphic. As a further main result we prove that the cutDedekindMacNeille completion of the order that belongs to the minimal decomposition of a relation is isomorphic to the concept lattice of that relation. Instead of considering binary relations on sets, we will work point-free within the general framework of allegories. This complement-free approach implies that the results of the paper can be applied to all models of these algebraic structures, including, for instance, lattice-valued fuzzy relations.
Data Linkage Algebra, Data Linkage Dynamics, and Priority Rewriting
Authors: Bergstra J.A. , Middelburg C.A.
Published: December 2019

We introduce an algebra of data linkages. Data linkages are intended for modelling the states of computations in which dynamic data structures are involved. We present a simple model of computation in which states of computations are modelled as data linkages and state changes take place by means of certain actions. We describe the state changes and replies that result from performing those actions by means of a term rewriting system with rule priorities. The model in question is an upgrade of molecular dynamics. The upgrading is mainly concerned with the features to deal with values and the features to reclaim garbage.
Bayesian Segmentation Based Local Geometrically Invariant Image Watermarking
Authors: Wang Xiangyang , Yang Hongying , Wang Jing , Chen Lili , Niu Panpan
Published: December 2019

Robust digital watermarking has been an active research topic in the last decade. As one of the promising approaches, feature point based image watermarking has attracted many researchers. However, the related work usually suffers from the following limitations: 1) The feature point detector is sensitive to texture region, and some noise feature points are always detected in the texture region. 2) The feature points focus too much on high contrast region, and the feature points are distributed unevenly. Based on Bayesian image segmentation, we propose a local geometrically invariant image watermarking scheme with good visual quality in this paper. Firstly, the Bayesian image segmentation is used to segment the host image into several homogeneous regions. Secondly, for each homogeneous region, image feature points are extracted using the multiscale Harris-Laplace detector, and the corresponding invariant local image regions are constructed adaptively. Finally, by taking the human visual system (HVS) into account, digital watermark is repeatedly embedded into local image regions by modulating the magnitudes of DFT coefficients. By binding the digital watermark with the invariant local image regions, the watermark detection can be done without synchronization error. Experimental results show that the proposed image watermarking is not only invisible and robust against common image processing operations such as sharpening, noise adding, and JPEG compression etc, but also robust against the geometric distortions.
Minimal Description and Maximal Description in Covering-based Rough Sets
Authors: Wang Zhaohao , Shu Lan , Ding Xiuyong
Published: December 2019

Rough set theory is an important technique in knowledge discovery in databases. In covering-based rough sets, seven types of rough set models were established in recent years. This paper defines the concept of maximal description of an element, and further explores the properties and structures of several types by means of the concepts of maximal description and minimal description. Finally, we study the relationship between covering-based rough sets and the generalized rough sets based on binary relation.
Cryptanalysis and Improvement of a Certificateless Multi-proxy Signature Scheme
Authors: Tian Miaomiao , Yang Wei , Huang Liusheng
Published: December 2019

Certificateless cryptography is a new type of public key cryptography, which removes the certificate management problem in traditional public key cryptography and the key escrow problem in identity-based public key cryptography. Multi-proxy signature is an extension of proxy signature, which allows an original signer authorizing a group of proxy signers and only the cooperation of all proxy signers in the group can create valid proxy signatures on behalf of the original signer. Recently, Jin and Wen combined certificateless cryptography with multi-proxy signature, and proposed a model as well as a concrete scheme of certificateless multi-proxy signature. They claimed that their scheme is provably secure in their security model. Unfortunately, in this paper by giving two attacks, we will show that their certificateless multi-proxy signature scheme can be broken. The first attack indicates their security model is flawed and the second attack indicates their certificateless multi-proxy signature scheme is insecure. Possible improvements are also suggested to prevent these attacks.
Rough Set Characterization for 2-circuit Matroid
Authors: Wang Shiping , Zhu Qingxin , Zhu William , Min Fan
Published: December 2019

Rough sets are efficient to extract rules from information systems. Matroids generalize the linear independency in vector spaces and the cycle in graphs. Specifically, matroids provide well-established platforms for greedy algorithms, while most existing algorithms for many rough set problems including attribute reduction are greedy ones. Therefore, the combination between rough sets and matroids may bring new efficient solutions to those important and difficult problems. In this paper, 2-circuit matroids, abstracted from matroidal characteristics of rough sets, are studied and axiomatized. A matroid is induced by an equivalence relation, and its characteristics including the independent set and duality are represented with rough sets. Based on these rough set representations, this special type of matroid is defined as 2-circuit matroids. Conversely, an equivalence relation is induced by a matroid, and its relationship with the above induction is further investigated. Finally, a number of axioms of the 2-circuit matroid are obtained through rough sets. These interesting and diverse axioms demonstrate the potential for the connection between rough sets and matroids.
A Robust Audio Watermarking Scheme using Higher-order Statistics in Empirical Mode Decomposition Domain
Authors: Wang Xian-gyang , Niu Pan-pan , Yang Hong-ying , Zhang Yan , Ma Tian-xiao
Published: December 2019

The development of a desynchronization invariant audio watermarking scheme without degrading acoustical quality is a challenging work. This paper proposes a robust audio watermarking scheme in Empirical Mode Decomposition (EMD) domain, in which the higher-order statistics and synchronization code are utilized. Firstly, the wavelet de-noising is performed on the original host audio, the de-noised digital audio is segmented, and then each segment is cut into two parts. Secondly, with the spatial watermarking technique, synchronization code is embedded into the statistics average value of audio samples in the first part. Thirdly, for the second part, EMD is performed, and a series of Intrinsic Mode Functions (IMFs) and a residual are given, and then the higher-order statistics of residual are obtained by using the Hausdorff distance. Finally, the digital watermark is embedded into the residual in EMD domain by using the higher-order statistics. Simulation results show that the proposed watermarking scheme is not only inaudible and robust against common signal processing operations such as MP3 compression, noise addition,resampling, and re-quantization etc, but also robust against the desynchronization attacks such as random cropping, amplitude variation, pitch shifting, and jittering etc.
Spaced Seed Design Using Perfect Rulers
Authors: Egidi Lavinia , Manzini Giovanni
Published: December 2019

A widely used class of approximate pattern matching algorithms work in two stages, the first being a filtering stage that uses spaced seeds to quickly discards regions where a match is not likely to occur. The design of effective spaced seeds is known to be a hard problem. In this setting, we propose a family of lossless spaced seeds for matching with up to two errors based on mathematical objects known as perfect rulers. We analyze these seeds with respect to the tradeoff they offer between seed weight and the minimum length of the pattern to be matched. We identify a specific property of rulers, namely their skewness, which is closely related to the minimum pattern length of the derived seeds. In this context, we study in depth the specific case of Wichmann rulers and investigate the generalization of our approach to the larger class of unrestricted rulers. Although our analysis is mainly of theoretical interest, we show that for pattern lengths of practical relevance our seeds have a larger weight, hence a better filtration efficiency, than the ones known in the literature.
Evolvability by Mimicking Common Properties of a Nervous System and Computer Software
Authors: Rataj Artur
Published: December 2019

We study, on the basis of a simple neural–network like system that we call a spatial network, how several properties of two evolvable systems: a nervous system and computer software, could influence on the evolvability of a genetic algorithm. The following properties are modelled: hierarchical modularity, mirroring, extensive variability and quantitative genetic traits. By mirroring we understand mimicking of the structure of processed data by the structure of the processing algorithm. We estimate the evolvability of several examples of the presented networks, which perform simple image processing tasks, like stereo–to–depth. The evaluation is done by studying the size of these networks' genotype.
Nominal Groups and Their Homomorphism Theorems
Authors: Alexandru Andrei , Ciobanu Gabriel
Published: December 2019

We introduce and study the nominal groups, providing some algebraic properties of this new structure. We focus on the properties of nominal homomorphisms, and study the correspondence between some results obtained in the Fraenkel-Mostowski framework (where only finitely supported objects are allowed) and those obtained in the classical Zermelo-Fraenkel framework.
The Measurable Space of Stochastic Processes
Authors: Cardelli Luca , Mardare Radu
Published: December 2019

We introduce a stochastic extension of CCS endowed with structural operational semantics expressed in terms of measure theory. The set of processes is organised as a measurable space by the sigma-algebra generated by structural congruence. The structural operational semantics associates to each process a set of measures over the space of processes. The measures encode the rates of the transitions from a process (state of a system) to a measurable set of processes. We prove that the stochastic bisimilarity is a congruence, which extends the structural congruence. In addition to an elegant operational semantics, our calculus provides a canonic way to define metrics on processes that measure how similar two processes are in terms of behaviour.
On Controlled P Systems
Authors: Krithivasan Kamala , Păun Gheorghe , Ramanujan Ajeesh
Published: December 2019

We introduce and briefly investigate P systems with controlled computations. First, P systems with label restricted transitions are considered (in each step, all rules used have either the same label, or, possibly, the empty label, λ), then P systems with the computations controlled by languages (as in context-free controlled grammars). The relationships between the families of sets of numbers computed by the various classes of controlled P systems are investigated, also comparing them with length sets of languages in Chomsky and Lindenmayer hierarchies (characterizations of the length sets of ET0L and of recursively enumerable languages are obtained in this framework). A series of open problems and research topics are formulated.
A New Multi-Step Backward Cloud Transformation Algorithm Based on Normal Cloud Model
Authors: Xu Changlin , Wang Guoyin , Zhang Qinghua
Published: December 2019

The representation and processing of uncertainty information is one of the key basic issues of the intelligent information processing in the face of growing vast information, especially in the era of network. There have been many theories, such as probability statistics, evidence theory, fuzzy set, rough set, cloud model, etc., to deal with uncertainty information from different perspectives, and they have been applied into obtaining the rules and knowledge from amount of data, for example, data mining, knowledge discovery, machine learning, expert system, etc. Simply, This is a cognitive transformation process from data to knowledge (FDtoK). However, the cognitive transformation process from knowledge to data (FKtoD) is what often happens in human brain, but it is lack of research. As an effective cognition model, cloud model provides a cognitive transformation way to realize both processes of FDtoK and FKtoD via forward cloud transformation (FCT) and backward cloud transformation (BCT). In this paper, the authors introduce the FCT and BCT firstly, and make a depth analysis for the two existing single-step BCT algorithms. We find that these two BCT algorithms lack stability and sometimes are invalid. For this reason we propose a new multi-step backward cloud transformation algorithm based on sampling with replacement (MBCT-SR) which is more precise than the existing methods. Furthermore, the effectiveness and convergence of new method is analyzed in detail, and how to set the parameters m, r appeared in MBCT-SR is also analyzed. Finally, we have error analysis and comparison to demonstrate the efficiency of the proposed backward cloud transformation algorithm for some simulation experiments.
A Novel Image Encryption Scheme Based on Generalized Multi-sawtooth Maps
Authors: Ye Ruisong
Published: December 2019

In this paper, a generalized multi-sawtooth map based image encryption scheme with an efficient permutation-diffusion mechanism is proposed. In the permutation process, a generalized multi-sawtooth map is utilized to generate one chaotic orbit used to get one index order sequence for the permutation of image pixel positions, while in the diffusion process, two generalized multi-sawtooth maps are employed to yield two pseudo-random grey value sequences for a two-way diffusion of pixel grey values. The yielded grey value sequences are not only sensitive to the control parameters and initial conditions of the considered chaotic maps, but also strongly depend on the plain-image processed, therefore the proposed scheme can effectively resist statistical attack, differential attack, known-plaintext as well as chosen-plaintext attack. Experimental results show that the new image encryption scheme has satisfactory security thanks to its large key space and robust permutation-diffusion mechanism, which makes it a potential candidate for designing image encryption schemes.
A Neuro-Fuzzy System Combined with Particle Swarm Optimization for Handwritten Character Recognition
Authors: Chang Bae-Muu
Published: December 2019

A novel character recognition method, called a Neuro-Fuzzy system combined with Particle swarm optimization for Handwritten Character Recognition (NFPHCR), is proposed in this paper. The NFPHCR method integrates Recurrent Neural Network (RNN), Fuzzy Inference System (FIS), and Particle Swarm Optimization (PSO) algorithm to recognize handwritten characters. It employs the RNN to effectively extract oriented features of handwritten characters, and then, these features are applied to create the FIS. Finally, the FIS combined with the PSO algorithm can powerfully estimate similarity ratings between the recognized character and sampling characters in the character database. Experimental results demonstrate that the NFPHCR method achieves a satisfying recognition performance and outperforms other existing methods under considerations.
Heuristic Rating Estimation Approach to The Pairwise Comparisons Method
Authors: Kułakowski Konrad
Published: December 2019

The Heuristic Ratio Estimation (HRE) approach proposes a new way of using the pairwise comparisons matrix. It allows the assumption that the weights of some alternatives (herein referred to as concepts) are known and fixed, hence the weight vector needs to be estimated only for the other unknown values. The main purpose of this paper is to extend the previously proposed iterative HRE algorithm and present all the heuristics that create a generalized approach. Theoretical considerations are accompanied by a few numerical examples demonstrating how the selected heuristics can be used in practice.
A Numerical Algorithm and a Variational Iteration Technique for Solving Higher Order Fuzzy Integro-differential Equations
Authors: Narayanamoorthy S. , Murugan K.
Published: December 2019

In this paper, we present an algorithmic form of the variational iteration method (VIM) to handle both linear and nonlinear higher order fuzzy integro-differential equations. Using parametric form of fuzzy numbers to convert higher order fuzzy integro-differential equation to a system of higher order integro-differential equations in crisp case. By using the variational integration method we find the approximate solution of this system and consequently we obtain an approximation for fuzzy solution of the higher order fuzzy integro-differential equations. The numerical results are examined.
Near Groups of Weak Cosets on Nearness Approximation Spaces
Authors: Öztürk Mehmet Ali , Uçkun Mustafa , İnan Ebubekir
Published: December 2019

In this paper, we consider the problem of how to establish algebraic structures of near sets on nearness approximation spaces. Essentially, our approach is define the near group of all weak cosets by considering an operation on the set of all weak cosets. Afterwards, our aim is to study near homomorphism theorems on near groups, and investigate some properties of near groups.
An Algorithmic-type Classification of Tetravalent One-regular Graphs Using Computer Algebra Tools
Authors: Ghasemi Mohsen
Published: December 2019

A finite graph is one-regular if its automorphism group acts regularly on the set of its arcs. In the present paper, tetravalent one-regular graphs of order 7p2, where p is a prime, are classified using computer algebra tools.
The Impact of a Bi-connected Graph Decomposition on Solving Cooperative Path-finding Problems
Authors: Surynek Pavel , Surynková Petra , Chromý Miloš
Published: December 2019

This paper proposes a framework for analyzing algorithms for inductive processing of bi-connected graphs. The BIBOX algorithm for solving cooperative path-finding problems over bi-connected graphs is submitted for the suggested analysis. The algorithm proceeds according to a decomposition of a given bi-connected graph into handles. After finishing a handle, the handle is ruled out of consideration and the processing task is reduced to a task of the same type on a smaller graph. The handle decomposition for which the BIBOX algorithm performs best is theoretically identified. The conducted experimental evaluation confirms that the suggested theoretical analysis well corresponds to the real situation.
Towards Assessment of Innovativeness Economy Determinant Correlation: the Double Self-Organizing Feature Map Approach
Authors: Czyżewska Marta , Szkoła Jarosław , Pancerz Krzysztof
Published: December 2019

In the paper, we attempt to identify the crucial determinants of innovativeness economy and the correlations between the determinants. We based our research on the Innovativeness Union Scoreboard (IUS) dataset. In order to solve the problem, we propose to use the Double Self-Organizing Feature Map (SOM) approach. In the first step, countries, described by determinants of innovativeness economy, are clustered using SOMs according to five year time series for each determinant separately. In the second step, results of the first step are clustered again using SOM to obtain the final correlation represented in the form of a minimal spanning tree. We propose some modifications of the clustering process using SOMs to improve classification results and efficiency of the learning process.
On the Complexity of the Reachability Problem for Safe, Elementary Hornets
Authors: Köhler-Bußmeier Michael
Published: December 2019

In this paper we study the complexity of HORNETS, an algebraic extension of object nets. We define a restricted class: safe, elementary HORNETS, to guarantee finite state spaces. It will turn out, that the reachability problem for this class requires exponential space, which is a major increase when compared to safe, elementary object nets, which require polynomial space.
Formal Description of Alvis Language with α0 System Layer
Authors: Szpyrka Marcin , Matyasik Piotr , Mrówka Rafał , Kotulski Leszek
Published: December 2019

The paper presents a formal description of a subset of the Alvis language designed for the modelling and formal verification of concurrent systems. Alvis combines possibilities of a formal models verification with flexibility and simplicity of practical programming languages. Alvis provides a graphical modelling of interconnections among agents and a high level programming language used for the description of agents behaviour. Its semantic depends on the so-called system layer. The most universal system layer α0, described in the paper, makes Alvis similar to other formal languages like Petri nets, process algebras, time automata, etc.
Universal Query Language for Unified State Model
Authors: Wiśniewski Piotr , Stencel Krzysztof
Published: December 2019

Unified State Model (USM) is a single data model that allows conveying objects of major programming languages and databases. USM exploits and emphasizes common properties of their data models. USM is equipped with mappings from these data models onto it. With USM at hand, we have faced the next natural research question whether numerous query languages for the data subsumed by USM can be clearly mapped onto a common language. We have designed and proposed such a language called the Unified Query Language (UQL). UQL is intended to be a minimalistic and elegant query language that allows expressing queries of languages of data models covered by USM. In this paper we define UQL and its concise set of operators. Next we conduct a mild introduction into UQL features by showing examples of SQL and ODMG OQL queries and their mapping onto UQL. We conclude by presenting the mapping of the theoretical foundations of these two major query languages onto UQL. They are the multiset relational algebra and the object query algebra. This is an important step towards the establishment of a fully-fledged common query language for USM and its subsumed data models.
The Incremental Maintenance of Transition Tour
Authors: Németh Gábor Árpád , Pap Zoltán
Published: December 2019

While evolutionary development methodologies have become increasingly prevalent, incremental testing methods are lagging behind. Most traditional test generation algorithms – including the Transition Tour method – rebuild test sequences from scratch even if minimal changes to the system have been made. In the current paper we propose two incremental algorithms to update a Transition Tour test sequence after changes in a deterministic finite state machine model. Our solution uses existing information – the Eulerian graph of a previous version of the system and an Euler tour in it – to update the test cases of the system in response to modification. The first algorithm keeps an Eulerian graph up to date, while the second algorithm maintains an Euler tour in the augmented graph. Analytical and practical analyses show that our algorithms are very efficient in the case of changing specifications. We also demonstrate our methods through an example.
Definability and Canonicity for Boolean Logic with a Binary Relation
Authors: Balbiani Philippe , Tinchev Tinko
Published: December 2019

This paper studies the concepts of definability and canonicity in Boolean logic with a binary relation. Firstly, it provides formulas defining first-order or second-order conditions on frames. Secondly, it proves that all formulas corresponding to compatible first-order conditions on frames are canonical.
Computing a Longest Common Palindromic Subsequence
Authors: Chowdhury Shihabur Rahman , Hasan Md. Mahbubul , Iqbal Sumaiya , Rahman M. Sohel
Published: December 2019

The longest common subsequence (LCS) problem is a classic and well-studied problem in computer science. Palindrome is a word which reads the same forward as it does backward. The longest common palindromic subsequence (LCPS) problem is a variant of the classic LCS problem which finds a longest common subsequence between two given strings such that the computed subsequence is also a palindrome. In this paper, we study the LCPS problem and give two novel algorithms to solve it. To the best of our knowledge, this is the first attempt to study and solve this problem.
Quadratic Algorithms for Testing of Codes and ◊-Codes
Authors: Han Nguyen Dinh , Vinh Ho Ngoc , Thang Dang Quyet , Huy Phan Trung
Published: December 2019

The Sardinas-Patterson's test for codes has contributed many effective testing algorithms to the development of theory of codes, formal languages, etc. However, we will show that a modification of this test proposed in this paper can deduce more effective testing algorithms for codes. As a consequence, we establish a quadratic algorithm that, given as input a regular language X defined by a tuple (�, M, B), where � : A* → M is a monoid morphism saturating X, M is a finite monoid, $B \subseteq M$, X = �−1(B), decides in time complexity $\mathcal{O}(n^2)$ whether X is a code, where n = Card(M). Specially, n can be chosen as the finite index of X. A quadratic algorithm for testing of ◊-codes is also established.
Unsupervised and Interactive Semi-supervised Clustering for Large Image Database Indexing and Retrieval
Authors: Lai Hien Phuong , Visani Muriel , Boucher Alain , Ogier Jean-Marc
Published: December 2019

The feature space structuring methods play a very important role in finding information in large image databases. They organize indexed images in order to facilitate, accelerate and improve the results of further retrieval. Clustering, one kind of feature space structuring, may organize the dataset into groups of similar objects without prior knowledge (unsupervised clustering) or with a limited amount of prior knowledge (semi-supervised clustering). In this paper, we present both formal and experimental comparisons of different unsupervised clustering methods for structuring large image databases. We use different image databases of increasing sizes (Wang, PascalVoc2006, Caltech101, Corel30k) to study the scalability of the different approaches. Then, we present a new interactive semi-supervised clustering model, which allows users to provide feedback in order to improve the clustering results according to their wishes. Moreover,we also compare, experimentally, our proposed model with the semi-supervised HMRF-kmeans clustering method.
Infinite Hierarchy of Permutation Languages
Authors: Madejski Grzegorz
Published: December 2019

Permutation grammars are an extension of context-free grammars with rules having the same symbols on both sides but possibly in a different order. An example of a permutation rule of length 3 is ABC → CBA. If these non-context-free rules are of length at most n, then we say that permutation grammar is of order n and all such grammars generate a family of permutation languages Permn. In 2010 Nagy showed that there exists a language such that it cannot be generated by a grammar of order 2, but rules of length 3 are enough. In other words, a strict inclusion $Perm_2 \subsetneq Perm_3$ was obtained. We extend this result proving that $Perm_{4n \minus 2} \subsetneq Perm_{4n \minus 1}$ for n ≥ 1.
Apriori-Based Rule Generation in Incomplete Information Databases and Non-Deterministic Information Systems
Authors: Sakai Hiroshi , Wu Mao , Nakata Michinori
Published: December 2019

This paper discusses issues related to incomplete information databases and considers a logical framework for rule generation. In our approach, a rule is an implication satisfying specified constraints. The term incomplete information databases covers many types of inexact data, such as non-deterministic information, data with missing values, incomplete information or interval valued data. In the paper, we start by defining certain and possible rules based on non-deterministic information. We use their mathematical properties to solve computational problems related to rule generation. Then, we reconsider the NIS-Apriori algorithm which generates a given implication if and only if it is either a certain rule or a possible rule satisfying the constraints. In this sense, NIS-Apriori is logically sound and complete. In this paper, we pay a special attention to soundness and completeness of the considered algorithmic framework, which is not necessarily obvious when switching from exact to inexact data sets. Moreover, we analyze different types of non-deterministic information corresponding to different types of the underlying attributes, i.e., value sets for qualitative attributes and intervals for quantitative attributes, and we discuss various approaches to construction of descriptors related to particular attributes within the rules' premises. An improved implementation of NIS-Apriori and some demonstrations of an experimental application of our approach to data sets taken from the UCI machine learning repository are also presented. Last but not least, we show simplified proofs of some of our theoretical results.
Distributed Timed Automata with Independently Evolving Clocks
Authors: Akshay S. , Bollig Benedikt , Gastin Paul , Mukund Madhavan , Kumar K. Narayan
Published: December 2019

We propose a model of distributed timed systems where each component is a timed automaton with a set of local clocks that evolve at a rate independent of the clocks of the other components. A clock can be read by any component in the system, but it can only be reset by the automaton it belongs to. There are two natural semantics for such systems. The universal semantics captures behaviors that hold under any choice of clock rates for the individual components. This is a natural choice when checking that a system always satisfies a positive specification. To check if a system avoids a negative specification, it is better to use the existential semantics—the set of behaviors that the system can possibly exhibit under some choice of clock rates. We show that the existential semantics always describes a regular set of behaviors. However, in the case of universal semantics, checking emptiness or universality turns out to be undecidable. As an alternative to the universal semantics, we propose a reactive semantics that allows us to check positive specifications and yet describes a regular set of behaviors.
A Horizontal Mesh Algorithm for a Class of Edge-bipartite Graphs and their Matrix Morsifications
Authors: Kaniecki Mariusz , Kosakowska Justyna , Malicki Piotr , Marczak Grzegorz
Published: December 2019

We construct a horizontal mesh algorithm for a study of a special type of mesh root systems of connected positive loop-free edge-bipartite graphs Δ, with n ≥ 2 vertices, in the sense of [SIAM J. Discrete Math. 27 (2013), 827–854] and [Fund. Inform. 124 (2013), 309-338]. Given such a loop-free edge-bipartite graph Δ, with the non-symmetric Gram matrix $\Gcaron_ \Delta \isin \mathbb{M}_n(\mathbb{Z})$ and the Coxeter transformation $\Phi_A : \mathbb{Z}^n \rarr \mathbb{Z}^n$ defined by a quasi-triangular matrix morsification $A \isin \mathbb{M}_n(\mathbb{Z})$ of Δ satisfying a non-cycle condition, our combinatorial algorithm constructs a ΦA-mesh root system structure $\Gamma(\Rscr_\Delta, \Phi_A)$ on the finite set of all ΦA-orbits of the irreducible root system $\Rscr_\Delta := {v \isin \mathbb{Z}^n; v \cdot \Gcaron_\Delta \cdot v^{tr} = 1}$ . We apply the algorithm to a graphical construction of a ΦI - mesh root system structure $\Gamma(\Rscr_I, \Phi_I)$ on the finite set of ΦI -orbits of roots of any poset I with positive definite Tits quadratic form $\qIcirc : \mathbb{Z}_I \rarr \mathbb{Z}$ .
On Projection Based Operators in lp Space for Exact Similarity Search
Authors: Wichert Andreas , Moreira Catarina
Published: December 2019

We investigate exact indexing for high dimensional lp norms based on the 1-Lipschitz property and projection operators. The orthogonal projection that satisfies the 1-Lipschitz property for the lp norm is described. The adaptive projection defined by the first principal component is introduced.
Description Languages for Relational Information Granules
Authors: Hońko Piotr
Published: December 2019

Information granulation is a powerful tool for data analysis and processing. However, not much attention has been devoted to application of this tool to data stored in a relational structure. This paper extends the notion of information granules to a relational case. Two information systems intended to store relational data are proposed. This study also extends a granule description language to express information granules derived from relational data. The proposed approach enables to analyze a given problem at different levels of granularity of relational data. This can find application in searching for patterns in data mining.
Tolerances Induced by Irredundant Coverings
Authors: Järvinen Jouni , Radeleczki Sándor
Published: December 2019

In this paper, we consider tolerances induced by irredundant coverings. Each tolerance R on U determines a quasiorder ≤R by setting x ≤R y if and only if R(x) ⊆ R(y). We prove that for a tolerance R induced by a covering H of U, the covering H is irredundant if and only if the quasiordered set (U,≤R) is bounded by minimal elements and the tolerance R coincides with the product ≥R ° ≤R. We also show that in such a case H = {↑m | m is minimal in (U,≤R)}, and for each minimal m, we have R(m) = ↑m. Additionally, this irredundant covering H inducing R consists of some blocks of the tolerance R. We give necessary and sufficient conditions under which H and the set of R-blocks coincide. These results are established by applying the notion of Helly numbers of quasiordered sets.