bluuebunny/crossref_metadata_2025 huggingface dataset:
A Tissue P Systems Based Uniform Solution to Tripartite Matching Problem
Authors: Niu Yunyun , Pan Linqiang , Pérez-Jiménez Mario J. , Font Miquel Rius
Published: December 2019

A tissue P system with cell division is a computing model which has two basic features: intercellular communication and the ability of cell division. The ability of cell division allows us to obtain an exponential amount of cells in linear time and to design cellular solutions to computationally hard problems in polynomial time. In this work we present an efficient solution to the tripartite matching problem by a family of such devices. This solution leads to an interesting open problem whether tissue P systems with cell division and communication rules of length 2 can solve NP-complete problems. An answer to this open problem will provide a borderline between efficiency and non-efficiency in terms of the lengths of communication rules.
Cryptanalysis of Two Efficient HIBE Schemes in the Standard Model
Authors: Wang Xu An , Yang Xiaoyuan , Zhang Minqing
Published: December 2019

In Informatica 32 (2008), Ren and Gu proposed an anonymous hierarchical identity based encryption scheme based on the q-ABDHE problem with full security in the standard model. Later in Indocrypt'08, they proposed another secure hierarchical identity based encryption scheme based on the q-TBDHE problem with full security in the standard model. They claimed that their schemes have short parameters, high efficiency and tight reduction. However, in this paper we give attacks to show their schemes are not secure at all. Concretely, from any first level private key, the adversary can easily derive a “private key” which can decrypt any ciphertexts for the target identity. That is to say, a query on any first level identity is enough to decrypt any ciphertext in the system.
Directed Overlap-inclusion Graphs as Representations of Ciliate Genes
Authors: Azimi Sepinoud , Harju Tero , Langille Miika , Petre Ion , Rogojin Vladimir
Published: December 2019

The simple intramolecular model for gene assembly in ciliates consists of three molecular operations based on local DNA manipulations. It was shown to predict correctly the assembly of all currently known ciliate gene patterns. Mathematical models in terms of signed permutations and signed strings proved limited in capturing some of the combinatorial details of the simple gene assembly process. A different formalization in terms of overlap-inclusion graphs, recently introduced by Brijder and Hoogeboom, proved well-suited to describe two of the three operations of the model and their combinatorial properties. We introduce in this paper an extension of the framework of Brijder and Hoogeboom in terms of directed overlap-inclusion graphs where more of the linear structure of the ciliate genes is described. We investigate a number of combinatorial properties of these graphs, including a necessary property in terms of forbidden induced subgraphs.
Limit Sets of Stable and Unstable Cellular Automata
Authors: Ballier Alexis , Guillon Pierre , Kari Jarkko
Published: December 2019

We construct a cellular automaton (CA) with a sofic and mixing limit set and then construct a stable CA with the same limit set, showing there exist subshifts that can be limit sets of both stable and unstable CAs, answering a question raised by A. Maass.
On Approximating Non-regular Languages by Regular Languages
Authors: Eisman Gerry , Ravikumar Bala
Published: December 2019

Approximate computation is a central concept in algorithms and computation theory. Our notion of approximation is that the algorithm performs correctly on most of the inputs. We propose some finite automata models to study the question of how well a finite automaton can approximately recognize a non-regular language. On the one hand, we show that there are natural problems for which a DFA can correctly solve almost all the instances, but not all instances. An example of such a problem is a decision question about the number of digits in the square of a given integer. On the other hand, we show that some languages (such as Lmajority = {x ∈ (0 + 1)* | x has more 1′s than 0′s }) can't be approximated by any regular language in a strong sense. We also show that there are problems that are intermediate (between the extremes stated above) in terms of how we well a regular language can approximate it. An example of such a problem is a decision question about the number of digits in the product of two integers. We also present results comparing different models of approximation.
Transition Complexity of Incomplete DFAs
Authors: Gao Yuan , Salomaa Kai , Yu Sheng
Published: December 2019

We consider the transition complexity of regular languages based on the incomplete deterministic finite automata. We establish tight bounds for the transition complexity of Boolean operations, in the case of union the upper and lower bounds differ by a multiplicative constant two. We show that the transition complexity results for union and complementation are very different from the state complexity results for the same operations. However, for intersection, the transition complexity bounds turn out to be similar to the corresponding bounds for state complexity.
Computational Complexity of NURIKABE
Authors: Holzer Markus , Klein Andreas , Kutrib Martin , Ruepp Oliver
Published: December 2019

We show that the popular pencil puzzle NURIKABE is intractable from the computational complexity point of view, that is, it is NP-complete, even when the involved numbers are 1 and 2 only. To this end, we show how to simulate Boolean gates by the puzzle under consideration. Moreover, we also study some NURIKABE variants, which remain NP-complete, too.
The Unique Decipherability in the Monoid of Regular Languages is Undecidable
Authors: Karhumäki Juhani , Saarela Aleksi
Published: December 2019

We show by a simple reduction that the unique decipherability problem in the language monoid of regular languages over a non-unary alphabet is undecidable.
Limited Asynchronous Spiking Neural P Systems
Authors: Pan Linqiang , Wang Jun , Hoogeboom Hendrik Jan
Published: December 2019

In a biological system, if a long enough time interval is given, an enabled chemical reaction will finish its reaction in the given time interval. With this motivation, it is natural to impose a bound on the time interval when an enabled spiking rule in a spiking neural P system (SN P system, for short) remains unused. In this work, a new working mode of SN P systems is defined, which is called limited asynchronous mode. In an SN P system working in limited asynchronous mode, if a rule is enabled at some step, this rule is not obligatorily used. From this step on, if the unused rule may be used later, it should be used in the given time interval. If further spikes make the rule non-applicable, then the computation continues in the new circumstances. The computation result of a computation in an SN P system working in limited asynchronous mode is defined as the total number of spikes sent into the environment by the system. It is proved that limited asynchronous SN P systems with standard spiking rules are universal. If the number of spikes present in each neuron of a limited asynchronous SN P system with standard spiking rules is bounded during a computation, then the power of a limited asynchronous SN P system with standard spiking rules falls drastically, and we get a characterization of semilinear sets of numbers.
Looking for Small Efficient P Systems
Authors: Pérez-Jiménez Mario J. , Riscos-Núñez Agustín , Rius-Font Miquel , Romero-Campero Francisco J.
Published: December 2019

In 1936 A. Turing showed the existence of a universal machine able to simulate any Turing machine given its description. In 1956, C. Shannon formulated for the first time the problem of finding the smallest possible universal Turing machine according to some critera to measure its size such as the number of states and symbols. Within the framework of Membrane Computing different studies have addressed this problem: small universal symport/antiport P systems (by considering the number of membranes, the weight of the rules and the number of objects as a measure of the size of the system), small universal splicing P systems (by considering the number of rules as a measure of the size of the system), and small universal spiking neural P systems (by considering the number of neurons as a measure of the size of the system). In this paper the problem of determining the smallest possible efficient P system is explicitly formulated. Efficiency within the framework of Membrane Computing refers to the capability of solving computationally hard problems (i.e. problems such that classical electronic computer cannot solve instances of medium/large size in any reasonable amount of time) in polynomial time. A descriptive measure to define precisely the notion of small P system is presented in this paper.
Universality of Splicing Test Tube Systems with Two Tubes
Authors: Verlan Sergey , Margenstern Maurice
Published: December 2019

Splicing test tube systems are one of the first distributed computing models based on splicing. The model introduces (test) tubes where the splicing operation is applied, which are arranged in a communication network with filters that permits to redistribute the words between the tubes at each step. We show that the computational completeness can be achieved with two tubes when the communication graph does not have self-loops. We also construct a universal splicing test tube system with 2 tubes having 23 rules.
On the Generative Power of ω-Grammars and ω-Automata
Authors: Chen Zhe
Published: December 2019

An ω-grammar is a formal grammar used to generate ω-words (i.e. infinite length words), while an ω-automaton is an automaton used to recognize ω-words. This paper gives clean and uniform definitions for ω-grammars and ω-automata, provides a systematic study of the generative power of ω-grammars with respect to ω-automata, and presents a complete set of results for various types of ω-grammars and acceptance modes. We use the tuple (σ, ρ, π) to denote various acceptance modes, where σ denotes that some designated elements should appear at least once or infinitely often, ρ denotes some binary relation between two sets, and π denotes normal or leftmost derivations. Technically, we propose (σ, ρ, π)-accepting ω-grammars, and systematically study their relative generative power with respect to (σ, ρ)-accepting ω-automata. We show how to construct some special forms of ω-grammars, such as ϵ-production-free ω-grammars. We study the equivalence or inclusion relations between ω-grammars and ω-automata by establishing the translation techniques. In particular, we show that, for some acceptance modes, the generative power of ω-CFG is strictly weaker than ω-PDA, and the generative power of ω-CSG is equal to ω-TM (rather than linear-bounded ω-automata-like devices). Furthermore, we raise some remaining open problems for two of the acceptance modes.
Solution to the Range Problem for Combinatory Logic
Authors: Intrigila Benedetto , Statman Richard
Published: December 2019

The λ-theory ℋ is obtained from β-conversion by identifying all closed unsolvable terms (or, equivalently, terms without head normal form). The range problem for the theory ℋ asks whether a closed term has always (up to equality in ℋ) either an infinite range or a singleton range (that is, it is a constant function). Here we give a solution to a natural version of this problem, giving a positive answer for the theory ℋ restricted to Combinatory Logic. The method of proof applies also to the Lazy λ-Calculus.
Rough Truth Degrees of Formulas and Approximate Reasoning in Rough Logic
Authors: She Yanhong , He Xiaoli , Wang Guojun
Published: December 2019

A propositional logic PRL for rough sets was proposed in [1]. In this paper, we initially introduce the concepts of rough (upper, lower) truth degrees on the set of formulas in PRL. Then, by grading the rough equality relations, we propose the concepts of rough (upper, lower) similarity degree. Finally, three different pseudo-metrics on the set of rough formulas are obtained, and thus an approximate reasoning mechanism is established.
Rainbow Induced Subgraphs in Proper Vertex Colorings
Authors: Kisielewicz Andrzej , Szykuła Marek
Published: December 2019

Given a graph H we define ρ(H) to be the minimum order of a graph G such that every proper vertex coloring of G contains a rainbow induced subgraph isomorphic to H. We give upper and lower bounds for ρ(H), compute the exact value for some classes of graphs, and consider an interesting combinatorial problem connected with computation of ρ(H) for paths. A part of this research has been guided by a computer search and, accordingly, some computational results are presented. A special motivation comes from research in on-line coloring.
On McNaughton Families of Languages That Are Specified by Some Variants of Monadic String-Rewriting Systems
Authors: Leupold Peter , Otto Friedrich
Published: December 2019

We study the McNaughton families of languages that are specified by four different variants of monadic string-rewriting systems: strictly monadic systems, monadic systems, inverse context-free systems, and generalized monadic systems. In the general case these four variants yield the same McNaughton family of languages, which coincides with the class of context-free languages. In the case of confluent systems, however, we obtain two McNaughton families by showing that special rules, that is, rules with empty right-hand side, are not needed. This implies that in this situation strictly monadic systems are as expressive as monadic systems, and inverse context-free systems are as expressive as generalized monadic systems. The McNaughton family defined by the former systems is contained in the McNaughton family that is defined by the latter systems, and this inclusion is proper if and only if the former family is not closed under inverse alphabetic morphisms. Finally, we show that the latter family is a proper subclass of the class of deterministic context-free languages.
Survey: Weighted Extended Top-down Tree Transducers Part II—Application in Machine Translation
Authors: Maletti Andreas
Published: December 2019

In this second part of the survey, we present the application of weighted extended top-down tree transducers in machine translation, which is the automatic translation of natural language texts. We present several formal properties that are relevant to machine translation and evaluate the weighted extended top-down tree transducer along those criteria. In addition, we demonstrate how to extract rules for an extended top-down tree transducer from existing linguistic data and how to obtain suitable rule weights automatically from similar information. Overall, the aim of the survey is twofold. It should provide a synopsis that illustrates how theory (tree transducers) and practice (machine translation) interact on this particular example. Secondly, it presents a uniform and simplified treatment of the rule extraction and training algorithms that is accessible to the nonexpert. Additional details can be found in the original results that are referenced throughout the text.
Relational Feature Mining with Hierarchical Multitask kFOIL
Authors: Cilia Elisa , Landwehr Niels , Passerini Andrea
Published: December 2019

We introduce hierarchical kFOIL as a simple extension of the multitask kFOIL learning algorithm. The algorithm first learns a core logic representation common to all tasks, and then refines it by specialization on a per-task basis. The approach can be easily generalized to a deeper hierarchy of tasks. A task clustering algorithm is also proposed in order to automatically generate the task hierarchy. The approach is validated on problems of drug-resistance mutation prediction and protein structural classification. Experimental results show the advantage of the hierarchical version over both single and multi task alternatives and its potential usefulness in providing explanatory features for the domain. Task clustering allows to further improve performance when a deeper hierarchy is considered.
Dynamic Coloring of Graphs
Authors: Borowiecki Piotr , Sidorowicz Elżbieta
Published: December 2019

Dynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN's, channel assignment in WDM optical networks as well as traffic scheduling. In the dynamic setting of the problem, a graph we color is not given in advance and new vertices together with adjacent edges are revealed one after another at algorithm's input during the coloring process. Moreover, independently of the algorithm, some vertices may lose their colors and the algorithm may be asked to color them again. We formally define a dynamic graph coloring problem, the dynamic chromatic number and prove various bounds on its value. We also analyze the effectiveness of the dynamic coloring algorithm Dynamic-Fit for selected classes of graphs. In particular, we deal with trees, products of graphs and classes of graphs for which Dynamic-Fit is competitive. Motivated by applications, we state the problem of dynamic coloring with discoloring constraints for which the performance of the dynamic algorithm Time-Fit is analyzed and give a characterization of graphs k-critical for Time-Fit. Since for any fixed k > 0 the number of such graphs is finite, it is possible to decide in polynomial time whether Time-Fit will always color a given graph with at most k colors.
A Graph Grammar Model of the hp Adaptive Three Dimensional Finite Element Method. Part II
Authors: Paszyńska Anna , Grabska Ewa , Paszyński Maciej
Published: December 2019

This paper presents a composite programmable graph grammar model of the three dimensional self-adaptive hp Finite Element Method (hp-FEM) algorithms. The computational mesh composed of hexahedral finite elements is represented by a composite graph. The operations performed over the mesh are expressed by composite graph grammar productions. The three dimensional model is based on the extension of the two dimensional model for rectangular finite elements. This paper is concluded with numerical examples, presenting the generation of the optimal mesh for simulation of the Step-and-Flash Imprint Lithography (SFIL), the modern patterning process.
Ellipse Invariant Algorithm for Texture Classification
Authors: Yao Chih-Chia , Lee Kang
Published: December 2019

The classification of texture images, especially those with spatial rotation and region shift, is a challenge and important problem in image analysis and classification. This paper proposes a novel algorithm design, an ellipse invariant algorithm, to improve the capability of texture classification for spatial rotation and region shift. The principle of an ellipse invariant algorithm is to use a minimum ellipse to enclose specific representative pixels extracted by the subtracting clustering method. After translating the coordinates, the ellipse in the rotated texture would be formulated as the ellipse in original texture. Also in this paper a hybrid texture filter is proposed. In the hybrid texture filter the scheme of texture feature extraction include Gabor wavelet, neighboring grey level dependence matrix and the ellipse invariant algorithm. Support vector machines (SVMs) are introduced as the classifier. The proposed hybrid texture filter can classify both the stochastic textures and structural textures. Experimental results reveal that this proposed algorithm outperforms existing design algorithms.
A Novel Steganographic Method with Four-Pixel Differencing and Modulus Function
Authors: Liao Xin , Wen Qiao-yan , Zhao Ze-li , Zhang Jie
Published: December 2019

To improve the stego-image quality and provide a larger embedding capacity, a novel steganographic method based on four-pixel differencing and modulus function is presented. We process a block of four neighboring pixels, and form three two-pixel groups to record the information of secret data. In each group, the difference value between two pixels is exploited to estimate how many secret bits will be embedded. Two pixels will be adjusted so that the sum of the remainders of them is equal to secret data. In order to extract the secret data exactly, four pixel values in a block are adjusted synchronously by using modulus function. An optimization problem is formulated to minimize the embedding distortion. A theoretical proof is given to ensure the solvability of the problem. The experimental results show the proposed method not only has a larger embedding capacity but also provides better stego-image quality.
A Label Correcting Algorithm for the Bus Routing Problem
Authors: Widuch Jacek
Published: December 2019

This paper proposes a label correcting algorithm for solving the bus routing problem (BRP). The goal of the BRP is finding a route from the start stop to the final stop minimizing the time and the cost of travel. Additionally the time of starting travel at the start stop is given. The problem belongs to the group of multicriteria optimization problems (MOP), whose the solution is a set of non-dominated solutions. The algorithm makes possible to find all routes which belong to the set of non-dominated solutions. Apart from that the results of experimental tests are presented.
Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program
Authors: Suchenek Marek A.
Published: December 2019

The worst-case behavior of the heap-construction phase of Heapsort escaped mathematically precise characterization by a closed-form formula for almost five decades. This paper offers a proof that the exact number of comparisons of keys performed in the worst case during construction of a heap of size N is: 2N − 2s2(N) − e2(N), where s2(N) is the sum of all digits of the binary representation of N and e2(N) is the exponent of 2 in the prime factorization of N. It allows for derivation of this best-known upper bound on the number of comparisons of Heapsort: (2N − 1)$\lceil$lgN$\rceil$ − 2$\lceil$lgN$\rceil$+1 − 2s2(N) − e2(N) + 5.
On Flooding in the Presence of Random Faults
Authors: Cichoń Jacek , Klonowski Marek
Published: December 2019

In this paper we study the efficiency of information flooding protocols in various communication networks, and in the presence of random faults. We show big differences between the flooding performance of networks with a seemingly similar structure. Since real-life systems usually consist of a moderate number of devices, the analysis presented in this paper is not limited to the asymptotic behavior of the flooding protocol. Instead, exact formulas are provided whenever possible. The presented results can be useful building blocks for the analysis of other, more sophisticated protocols. In particular, they may be used for planning and analyzing sensors network deployed in an environment subject to communication failures.
Left Random Context ET0L Grammars
Authors: Meduna Alexander , Zemek Petr
Published: December 2019

Consider ET0L grammars. Modify them such that a set of permitting symbols and a set of forbidding symbols are attached to each of their rules, just like in random context grammars. A rule like this can rewrite a symbol if each of its permitting symbols occurs to the left of the symbol to be rewritten in the current sentential form while each of its forbidding symbols does not occur there. ET0L grammars modified in this way are referred to as left random context ET0L grammars, and they represent the principal subject of the investigation in this paper. We prove that these grammars characterize the family of recursively enumerable languages, and without erasing rules, they characterize the family of context-sensitive languages. We also introduce a variety of special cases of these grammars and establish their generative power. In the conclusion, we put all the achieved results into the context of formal language theory as a whole and formulate several open questions.
The Complexity of Szilard Languages of Matrix Grammars Revisited
Authors: Cojocaru Liliana , Mäkinen Erkki
Published: December 2019

The regulated rewriting mechanism is one of the most efficient methods to augment the Chomsky hierarchy with a large variety of language classes. In this paper we investigate the derivation mechanism in regulated rewriting grammars such as matrix grammars, by studying their Szilard languages. We focus on the complexity of Szilard languages associated with unrestricted and leftmost-like derivations in matrix grammars, with or without appearance checking. The reason is twofold. First, to relate these classes of languages to parallel complexity classes such as 𝒩𝒞1 and 𝒜𝒞1, and, second, to improve some previous results. We prove that unrestricted Szilard languages and certain leftmost Szilard languages of context-free matrix grammars, without appearance checking, can be accepted by indexing alternating Turing machines in logarithmic time and space. Consequently, these classes are included in UE*-uniform 𝒩𝒞1. Unrestricted Szilard languages of matrix grammars with appearance checking can be accepted by deterministic Turing machines in 𝒪(n log n) time and 𝒪(log n) space. Leftmost-like Szilard languages of context-free matrix grammars, with appearance checking, can be recognized by nondeterministic Turing machines by using the same time and space resources. Hence, all these classes are included in 𝒜𝒞1.
Toroidal Algorithms for Mesh Geometries of Root Orbits of the Dynkin Diagram $\mathbb{D}_4$
Authors: Simson Daniel
Published: December 2019

By applying symbolic and numerical computation and the spectral Coxeter analysis technique of matrix morsifications introduced in our previous paper [Fund. Inform. 124(2013)], we present a complete algorithmic classification of the rational morsifications and their mesh geometries of root orbits for the Dynkin diagram $\mathbb{D}_4$. The structure of the isotropy group $Gl(4, \mathbb{Z})_{\mathbb{D}_4}$ of $\mathbb{D}_4$ is also studied. As a byproduct of our technique we show that, given a connected loop-free positive edge-bipartite graph Δ, with n ≥ 4 vertices (in the sense of our paper [SIAM J. Discrete Math. 27(2013)]) and the positive definite Gram unit form $q_\Delta : \mathbb{Z}^n \rightarrow \mathbb{Z}$, any positive integer d ≥ 1 can be presented as d = qΔ(v), with $v \in \mathbb{Z}^n$. In case n = 3, a positive integer d ≥ 1 can be presented as d = qΔ(v), with $v \in \mathbb{Z}^n$, if and only if d is not of the form 4a(16 · b + 14), where a and b are non-negative integers.
Wide-diameter of Product Graphs
Authors: Erveš Rija , Žerovnik Janez
Published: December 2019

The product graph B * F of graphs B and F is an interesting model in the design of large reliable networks. Fault tolerance and transmission delay of networks are important concepts in network design. The notions are strongly related to connectivity and diameter of a graph, and have been studied by many authors. Wide diameter of a graph combines studying connectivity with the diameter of a graph. Diameter with width k of a graph G, k-diameter, is defined as the minimum integer d for which there exist at least k internally disjoint paths of length at most d between any two distinct vertices in G. Denote by $\cal{D}^W_c (G)$ the c-diameter of G and κ(G) the connectivity of G. We prove that $\cal{D}^W_{a+b}(B * F) \le r_a(F) + \cal{D}^W_b (B) + 1$ for a ≤ κ(F) and b ≤ κ(B). The Rabin number rc(G) is the minimum integer d such that there are c internally disjoint paths of length at most d from any vertex v to any set of c vertices {v1, v2, ... , vc}.
Algebra of Rough Sets based on Quasi Order
Authors: Nagarajan E.K.R. , Umadevi D.
Published: December 2019

In this paper, we give a characterization theorem for rough sets based on quasi order. We obtain an algebra on the rough sets system determined by a quasi order which is the generalization of the algebra of rough sets system determined by an equivalence relation given in [1]. The properties of this algebra are abstracted at various levels and define new class of algebras. Further we give a representation theorem for the new class of algebras.
A Logic Framework for Incremental Learning of Process Models
Authors: Ferilli Stefano , Esposito Floriana
Published: December 2019

Standardized processes are important for correctly carrying out activities in an organization. Often the procedures they describe are already in operation, and the need is to understand and formalize them in a model that can support their analysis, replication and enforcement. Manually building these models is complex, costly and error-prone. Hence, the interest in automatically learning them from examples of actual procedures. Desirable options are incrementality in learning and adapting the models, and the ability to express triggers and conditions on the tasks that make up the workflow. This paper proposes a framework based on First-Order Logic that solves many shortcomings of previous approaches to this problem in the literature, allowing to deal with complex domains in a powerful and flexible way. Indeed, First-Order Logic provides a single, comprehensive and expressive representation and manipulation environment for supporting all of the above requirements. A purposely devised experimental evaluation confirms the effectiveness and efficiency of the proposed solution.
A Reliable Real-time Multicast Authentication Protocol with Provable Accuracy
Authors: Chang Chin-Chen , Cheng Ting-Fang
Published: December 2019

With the rapid development of network technologies and the continuing growth of the online population, the distribution of streamed media on the Internet has become a cause for concern. In order to securely deliver large-scale message streams, various multicast authentication protocols have been proposed. Recently, Abdellatif et al. proposed a real-time multicast authentication protocol called LAR1. The LAR1 protocol has low computation and communication overheads and uses the erasure code function to deal with the packet loss problem. However, through careful analyses, we find that their scheme cannot resist impersonation attacks on signers and only partially solves the packet loss problem. Moreover, there are still some design weaknesses. Then, we propose a more secure multicast authentication protocol, called IMA, with almost the same computation overheads and lower communication overheads. We adopt the BAN logic to demonstrate the authentication accuracy of our proposed scheme. Comparisons of other related works show that our proposed IMA protocol maintains efficiency and is more secure. Therefore, our proposed protocol is more suitable for practical applications.
Monteiro Spaces and Rough Sets Determined by Quasiorder Relations: Models for Nelson algebras
Authors: Järvinen Jouni , Radeleczki Sándor
Published: December 2019

The theory of rough sets provides a widely used modern tool, and in particular, rough sets induced by quasiorders are in the focus of the current interest, because they are strongly interrelated with the applications of preference relations and intuitionistic logic. In this paper, a structural characterisation of rough sets induced by quasiorders is given. These rough sets form Nelson algebras defined on algebraic lattices. We prove that any Nelson algebra can be represented as a subalgebra of an algebra defined on rough sets induced by a suitable quasiorder. We also show that Monteiro spaces, rough sets induced by quasiorders and Nelson algebras defined on T0-spaces that are Alexandrov topologies can be considered as equivalent structures, because they determine each other up to isomorphism.
NAO Soccer Robots Path Planning Based on Rough Mereology
Authors: Przytuła Łukasz
Published: December 2019

Soccer game is a good playground for testing artificial intelligence of robots and methods for spatial reasoning in real conditions. Decision making and path planning are only two of many tasks performed while playing soccer. This paper describes an application of rough mereology introduced by Polkowski and Skowron (1994) for path planning in robotic soccer game. Our path planning method was based on mereological potential fields introduced by Polkowski and Ośmiałowski (2008) and Ośmiałowski (2009) but was redesigned due to conditions of dynamic soccer environment, so an entirely new method was developed.
Reaction System Models for the Heat Shock Response
Authors: Azimi Sepinoud , Iancu Bogdan , Petre Ion
Published: December 2019

Reaction systems are a formal framework for modeling processes driven by biochemical reactions. They are based on the mechanisms of facilitation and inhibition. A main assumption is that if a resource is available, then it is present in sufficient amounts and as such, several reactions using the same resource will not compete concurrently against each other; this makes reaction systems very different as a modeling framework than traditional frameworks such as ODEs or continuous time Markov chains. We demonstrate in this paper that reaction systems are rich enough to capture the essential characteristics of ODE-based models. We construct a reaction system model for the heat shock response in such a way that its qualitative behavior correlates well with the quantitative behavior of the corresponding ODE model. We construct our reaction system model based on a novel concept of dominance graph that captures the competition on resources in the ODE model. We conclude with a discussion on the expressivity of reaction systems as compared to that of ODE-based models.
Can Machine Learning Learn a Decision Oracle for NP Problems? A Test on SAT
Authors: Grozea Cristian , Popescu Marius
Published: December 2019

This note describes our experiments aiming to empirically test the ability of machine learning models to act as decision oracles for NP problems. Focusing on satisfiability testing problems, we have generated random 3-SAT instances and found out that the correct branch prediction accuracy reached levels in excess of 99%. The branching in a simple backtracking-based SAT solver has been reduced in more than 90% of the tested cases, and the average number of branching steps has reduced to between 1/5 and 1/3 of the one without the machine learning model. The percentage of SAT instances where the machine learned heuristic-enhanced algorithm solved SAT in a single pass reached levels of 80-90%, depending on the set of features used.
Deciding Whether or Not a Synchronous Relation is Regular Prefix
Authors: Choffrut Christian
Published: December 2019

Eilenberg and al. introduced and studied in the late sixties the family of n-ary relations over the free monoid recognized by finite n-tape automata where the where the n reading heads tapes move simultaneously from left to right. We call these relations synchronous. In the eighties Angluin and Hoover and then Läuchli and Savioz introduced a proper subfamily which the first authors called regular prefix. Our main result shows that given a synchronous relation it is decidable whether or not it is regular prefix. Incidentally we also show that the family of regular prefix relations is uniformizable in the sense that all such relations contain a partial function with the same domain whose graph is a regular prefix relation.
On Axiomatization of Inconsistency Indicators for Pairwise Comparisons
Authors: Koczkodaj Waldemar W. , Szwarc Ryszard
Published: December 2019

This study examines the notion of inconsistency in pairwise comparisons for providing an axiomatization for it. It also proposes two inconsistency indicators for pairwise comparisons. The primary motivation for the inconsistency reduction is expressed by a computer industry concept “garbage in, garbage out”. The quality of the output depends on the quality of the input.
Extended Generalized Hyperbolic-function Method and New Exact Solutions of the Generalized Hamiltonian and NNV Equations by the Symbolic Computation
Authors: Liu Jian-Guo , Zeng Zhi-Fang
Published: December 2019

In this paper, with the aid of the computerized symbolic computation, we present an extended generalized hyperbolic-function method. Being concise and straightforward, it can be applicable to seek more types of solutions for certain nonlinear evolution equations (NLEES). In illustration, we choose the generalized Hamiltonian equations and the (2 + 1)-dimensional Nizhnik-Novikov-Veselov (NNV) equations to demonstrate the validity and advantages of the method. As a result, abundant new exact solutions are obtained including soliton-like solutions, traveling wave solutions etc. The method can be also applied to other nonlinear partial differential equations (NPDEs).
Combinatorial Algorithms for Computing Degenerations of Modules of Finite Dimension
Authors: Mróz Andrzej , Zwara Grzegorz
Published: December 2019

We present combinatorial algorithms for solving three problems that appear in the study of the degeneration order ≤deg for the variety of finite-dimensional modules over a k-algebra Λ, where M ≤deg N means that a module N belongs to an orbit closure $\overline{\cal{O}(M)}$ of a module M in the variety of Λ-modules. In particular, we introduce algorithmic techniques for deciding whether or not the relation M ≤deg N holds and for determining all predecessors (resp. succesors) of a given module M with respect to ≤deg. The order ≤deg plays an important role in modern algebraic geometry and module theory. Applications of our technique and experimental tests for particular classes of algebras are presented. The results show that a computer algebra technique and algorithmic computer calculations provide important tools in solving theoretical mathematics problems of high computational complexity. The algorithms are implemented and published as a part of an open source GAP package called QPA.
Non-probabilistic Solutions of Uncertain Fractional Order Diffusion Equations
Authors: Tapaswini Smita , Chakraverty S.
Published: December 2019

This paper investigates the numerical solution of uncertain fractional order diffusion equation subject to various external forces. Homotopy Perturbation Method (HPM) is used for the analysis. Uncertainties present in the system are modelled through triangular convex normalised fuzzy sets. A new computational technique has been proposed based on double parametric form of fuzzy numbers to handle the fuzzy fractional diffusion equation. Using the single parametric form of fuzzy numbers, the original fuzzy fractional diffusion equation is converted first to an interval fuzzy fractional differential equation. Next this equation is transformed to crisp form by applying double parametric form of fuzzy numbers. Finally the same is solved by HPM symbolically to obtain the uncertain bounds of the solution. Obtained results are depicted in term of plots. Results obtained by the proposed method are compared with existing results in special cases.
A Generic Methodological Framework for Cyber-ITS: Using Cyber-infrastructure in ITS Data Analysis Cases
Authors: Xia Yingjie , Zhang Ting , Wang Shengbao
Published: December 2019

This paper presents a method to capture the computational intensity and computing resource requirements of data analysis in intelligent transportation systems (ITS). These requirements can be transformed into a generic methodological framework for Cyber-ITS, mainly consisting of region-based ITS data divisions and tasks scheduling for processing, to support the efficient use of cyber-infrastructure (CI). To characterize the computational intensity of a particular ITS data analysis, the computational transformation is performed by data-centric and operation-centric transformation functions. The application of this framework is illustrated by two ITS data analysis cases: multi-sensor data fusion for traffic state estimation by integrating rough set theory with Dempster-Shafer (D-S) evidence theory, and geospatial computation on Global Positioning System (GPS) data for advertising value evaluation. To make the design of generic parallel computing solutions feasible for ITS data analysis in these cases, an approach is developed to decouple the region-based division from specific high performance computer (HPC) architecture and implement a prototype of the methodological framework. Experimental results show that the prototype implementation of the framework can be applied to divide the ITS data analysis into a load-balanced set of computing tasks, therefore facilitating the parallelized data fusion and geospatial computation to achieve remarkable speedup in computation time and throughput, without loss in accuracy.
Closed Sets in Occurrence Nets with Conflicts
Authors: Bernardinello Luca , Ferigato Carlo , Haar Stefan , Pomello Lucia
Published: December 2019

The semantics of concurrent processes can be defined in terms of partially ordered sets. Occurrence nets, which belong to the family of Petri nets, model concurrent processes as partially ordered sets of occurrences of local states and local events. On the basis of the associated concurrency relation, a closure operator can be defined, giving rise to a lattice of closed sets. Extending previous results along this line, the present paper studies occurrence nets with forward conflicts, modelling families of processes. It is shown that the lattice of closed sets is orthomodular, and the relations between closed sets and some particular substructures of an occurrence net are studied. In particular, the paper deals with runs, modelling concurrent histories, and trails, corresponding to possible histories of sequential components. A second closure operator is then defined by means of an iterative procedure. The corresponding closed sets, here called ‘dynamically closed’, are shown to form a complete lattice, which in general is not orthocomplemented. Finally, it is shown that, if an occurrence net satisfies a property called B-density, which essentially says that any antichain meets any trail, then the two notions of closed set coincide, and they form a complete, algebraic orthomodular lattice.
Computations in Boolean Algebra with Approximation
Authors: Kostanyan Armen , Khnkoyan Paruyr
Published: December 2019

Computations in Boolean algebra extended by adding an undefined element are investigated in the present paper. These computations (also known as approximative computations) are based on Lukasiewicz three-valued logic and are widely used in those applications where it is necessary to perform logical operations under uncertainty. The approximative computations are carried out as follows: if all instantiations of undefined operands produce the same result then this ascertained result is taken as final; otherwise, the final result is defined to be unknown. The key question in theory of approximative computations is whether a given Boolean formula is closed in the sense that the stepwise approximative computations in compliance with a given formula produce a result as accurate as possible. This question is investigated for the classes of disjunctive and algebraic normal forms.
A Robust Digital Watermarking Based on Local Complex Angular Radial Transform
Authors: Niu Pan-pan , Wang Xiang-yang , Yang Hong-ying , Wang Pei , Wang Ai-long
Published: December 2019

Geometric distortions that cause displacement between embedding and detection are usually difficult for watermark to survive. It is a challenging work to design a robust image watermarking scheme against geometric distortions, especially for local geometric distortions. Based on probability density and complex angular radial transform theory, a new image watermarking algorithm robust to geometric distortions is proposed in this paper. We firstly extract the steady image feature points by using new image feature point detector, which is based on the probability density. Then we build the affine invariant local feature regions based on probability density auto-correlation matrix. And finally, we present a new image watermarking algorithm robust to geometric distortions, in which the digital watermark is embedded into the local complex angular radial transform (CART) coefficients. Experiments results show that the proposed image watermarking is not only invisible and robust against common image processing operations, but also robust against the geometric distortions.
Quantitative Analysis of Lattice-valued Kripke Structures
Authors: Pan Haiyu , Zhang Min , Wu Hengyang , Chen Yixiang
Published: December 2019

To model and analyze systems with multi-valued information, in this paper, we present an extension of Kripke structures in the framework of complete residuted lattices, which we will refer to as lattice-valued Kripke structures (LKSs). We then show how the traditional trace containment and equivalence relations, can be lifted to the lattice-valued setting, and we introduce two families of lattice-valued versions of the relations. Further, we explore some interesting properties of these relations. Finally, we provide logical characterizations of our relations by a natural extension of linear temporal logic.
Content-based Image Retrieval using Visual Attention Point Features
Authors: Wang Xiang-Yang , Li Yong-Wei , Niu Pan-Pan , Yang Hong-Ying , Li Dong-Ming
Published: December 2019

One of the challenges in the development of a content-based image indexing and retrieval application is to achieve an efficient and robust indexing scheme. Color is a fundamental image feature used in content-based image retrieval (CBIR) systems. This paper proposes a robust and effective image retrieval scheme, which is based on the weighed color histogram of visual attention points. Firstly, the fully affine invariant visual attention points are extracted from the origin color image by using the Affine-SIFT (scale-invariant feature transform) detector. Secondly, according to the color complexity measure (CCM) theory, the visual weight values for the significant visual attention points are calculated to reflect the image local variation. Then, the weighed color histogram of visual attention points is constructed. Finally, the similarity between color images is computed by using the weighed color histogram of visual attention points. Experimental results show that the proposed image retrieval is not only more accurate and efficient in retrieving the user-interested images, but also yields higher retrieval accuracy than some state-of-the-art image retrieval schemes for various test DBs.
Using Domain Knowledge in Initial Stages of KDD: Optimization of Compound Object Processing
Authors: Szczuka Marcin , Sosnowski Łukasz , Krasuski Adam , Kreński Karol
Published: December 2019

We present a set of guidelines for improving quality and efficiency in initial steps of the KDD process by utilizing various kinds of domain knowledge. We discuss how such knowledge may be used to the advantage of system developer and what kinds of improvements can be achieved. We focus on systems that incorporate creation and processing of compound data objects within the RDBMS framework. These basic considerations are illustrated with several examples of implemented database solutions.
Fast Scalar Multiplications on the Curve v2 = up − au − b over the Finite Field of Characteristic p
Authors: You Lin , Yang Yilin , Gao Shuhong , Sang Yongxuan
Published: December 2019

Hyperelliptic curves have been widely researched for cryptographic applications, and some special hyperelliptic curves are often considered for practical applications. For efficient implementation of hyperelliptic curve cryptosystems, it is crucial to have efficient scalar multiplication in the Jacobian groups. For the hyperelliptic curve Cq: v2 = up − au − b over the field $\Fopf_{q}$ with q a power of an odd prime p, Duursma and Sakurai (2000) presented a scalar multiplication algorithm for q = p, a = 1 and b ∈ $\Fopf_{p}$. In this paper, by introducing the concept of simple divisors, we prove that a general divisor can be decomposed into the sum of some simple divisors. Based on this fact, we present a formula for p-scalar multiplications for any reduced divisor, then we give two efficient algorithms to speed up scalar multiplications for any parameters a and b over any extension of $\Fopf_{p}$. Compared with the signed binary method, the computations of our algorithms cost 55% to 76% less.