bluuebunny/crossref_metadata_2025 huggingface dataset:
A Note on a priori Estimations of Classification Circuit Complexity
Authors: Albrecht Andreas A. , Chashkin Alexander V. , Iliopoulos Costas S. , Kasim-Zade Oktay M. , Lappas Georgios , Steinhöfel Kathleen K.
Published: December 2019

The paper aims at tight upper bounds on the size of pattern classification circuits that can be used for a priori parameter settings in a machine learning context. The upper bounds relate the circuit size S(C) to nL := [log2mL], where mL is the number of training samples. In particular, we show that there exist unbounded fan-in threshold circuits with less than (a) SRcc := 2·√2nL + 3 gates for unbounded depth, (b) SLcc := 34.8 · √2nL + 14 · nL − 11 · log2nL + 2 gates for small bounded depth, where in both cases all mL samples are classified correctly. We note that the upper bounds do not depend on the length n of input (sample) vectors. Since nL << n in real-world problem settings, the upper bounds return values that are suitable for practical applications. We provide experimental evidence that the circuit size estimations work well on a number of pattern classification tasks. As a result, we formulate the conjecture that [1.25 · SRcc or [0.07 · SLcc] gates are sufficient to achieve a high generalization rate of bounded-depth classification circuits.
Extended Nondeterministic Finite Automata
Authors: Melnikov Boris
Published: December 2019

We consider a new expansion of nondeterministic finite automata. The goals of this consideration are: to apply some algorithms of such expansion for various problems of minimization of classical nondeterministic automata; to use such automata for describing practical anytime algorithms for the same problems of minimization; using such automata, we often can simplify some proofs for algorithms of simplification of usual nondeterministic automata.
Once More on the Edge-Minimization of Nondeterministic Finite Automata and the Connected Problems
Authors: Melnikov Boris
Published: December 2019

We consider in this paper the problem of edge-minimization for nondeterministic finite automata and some connected questions. We shall formulate a new algorithm solving this problem; this algorithm is a simplification of two ones published before. The connected problems include at first algorithms of combining states. We formulate some new sufficient conditions for the possibility of such combining.
Univariate Equations Over Sets of Natural Numbers
Authors: Jeż Artur , Okhotin Alexander
Published: December 2019

It is shown that equations of the form �(X) = ψ(X), in which the unknown X is a set of natural numbers and �, ψ use the operations of union, intersection and addition of sets S + T = {m + n |, m ∈ S, n ∈ T}, can simulate systems of equations �j(X1, …, Xn) = �j(X1, …, Xn) with 1 ≤ j ≤ ℓ, in the sense that solutions of any such system are encoded in the solutions of the corresponding equation. This implies computational universality of least and greatest solutions of equations �(X) = ψ(X), as well as undecidability of their basic decision problems. It is sufficient to use only singleton constants in the construction. All results equally apply to language equations over a one-letter alphabet Σ = {a}.
A Convergence Proof for the Particle Swarm Optimiser
Authors: van den Bergh Frans , Engelbrecht Andries Petrus
Published: December 2019

The Particle Swarm Optimiser (PSO) is a population based stochastic optimisation algorithm, empirically shown to be efficient and robust. This paper provides a proof to show that the original PSO does not have guaranteed convergence to a local optimum. A flaw in the original PSO is identified which causes stagnation of the swarm. Correction of this flaw results in a PSO algorithm with guaranteed convergence to a local minimum. Further extensions with provable global convergence are also described. Experimental results are provided to elucidate the behavior of the modified PSO as well as PSO variations with global convergence.
Equivalence of Processes in Partially Commutative Object-Oriented Environments
Authors: Grigoryan Hayk , Shoukourian Arsen
Published: December 2019

In this paper, the functional equivalence problem for processes, which is an important constituent of process optimization, is considered in object-oriented environments. Two basic cases are investigated: when the turn of operations execution is not essential for some objects while it is essential for the rest of them. In the first case, those objects are named commutative. Environments with both commutative and non-commutative objects are named partially commutative. It is shown, that the equivalence problem of processes in partially commutative environments that contain two or more commutative objects with more than one operation is unsolvable. The largest class of partially commutative environments is outlined where the equivalence problem is solvable (decidable). It is shown, that if there is only one object with two or more operations among commutative objects then the equivalence problem is solvable.
Structural Feature-Based Image Hashing and Similarity Metric for Tampering Detection
Authors: Tang Zhenjun , Wang Shuozhong , Zhang Xinpeng , Wei Weimin
Published: December 2019

Structural image features are exploited to construct perceptual image hashes in this work. The image is first preprocessed and divided into overlapped blocks. Correlation between each image block and a reference pattern is calculated. The intermediate hash is obtained from the correlation coefficients. These coefficients are finally mapped to the interval [0, 100], and scrambled to generate the hash sequence. A key component of the hashing method is a specially defined similarity metric to measure the “distance” between hashes. This similarity metric is sensitive to visually unacceptable alterations in small regions of the image, enabling the detection of small area tampering in the image. The hash is robust against content-preserving processing such as JPEG compression, moderate noise contamination, watermark embedding, re-scaling, brightness and contrast adjustment, and low-pass filtering. It has very low collision probability. Experiments are conducted to show performance of the proposed method.
Cryptanalysis of an Identity Based Signcryption without Random Oracles
Authors: Xiong Hu , Qin Zhiguang , Li Fagen
Published: December 2019

Signcryption is a cryptographic primitive that performs digital signature and public key encryption simultaneously, at lower computational costs and communication overhead than signing and encrypting separately. Recently, Yu et al. proposed an identity based signcryption scheme with a claimed proof of security. We show that their scheme is not secure even against a chosen-plaintext attack.
Reversible Steganography for BTC-compressed Images
Authors: Chang Chin-Chen , Lin Chih-Yang , Fan Yi-Hsuan
Published: December 2019

Reversible steganography becomes a popular hiding problem in recent years. A reversible steganographicmethod can reconstruct an original image without loss from the stego-image after extracting the embedded data. Unlike traditional reversible methods in which data is hidden in uncompressed images, we propose a reversible scheme for BTC (block truncation coding)-compressed images. The secret data embedded in the compressed image are more difficult to detect than in the uncompressed image. To achieve reversibility, the properties of side matching and BTC-compressed code are applied. The experimental results show that the proposed method is feasible for BTC-compressed images and can embed one more bit in each BTC-encoded block.
P Systems with Insertion and Deletion Exo-Operations
Authors: Alhazov Artiom , Krassovitskiy Alexander , Rogozhin Yurii , Verlan Sergey
Published: December 2019

It is known that insertion-deletion (P) systems with two symbols context-free insertion and deletion rules are not computationally complete. It is thus interesting to consider conditions that would allow such systems to reach computational completeness. In this paper we consider insertion-deletion P systems with insertion and deletion operations applied only at the ends of string (we call them exo-operations). We show that such systems with one-symbol insertion and deletion of up to two symbols are computationally complete, and so are systems with insertion of up to two symbols and one-symbol deletion. The question about the computational power of insertion-deletion P systems with one-symbol insertion and one-symbol deletion operations applied at the ends of string is open. However, the tissue P systems reach computationally completeness even in this case.
On the Hardness of Reoptimization with Multiple Given Solutions
Authors: Böckenhauer Hans-Joachim , Hromkovič Juraj , Sprock Andreas
Published: December 2019

In reoptimization, we consider the following scenario: Given an instance of a hard optimization problem together with an optimal solution for it, we want to solve a locally modified instance of the problem. It has recently been shown for several hard optimization problems that their corresponding reoptimization variants remain 𝒩𝒫-hard or even hard to approximate whereas they often admit improved approximation ratios. In this paper, we investigate a generalization of the reoptimization concept where we are given not only one optimal solution but multiple optimal solutions for an instance. We prove, for some variants of the Steiner tree problem and the traveling salesman problem, that the known reoptimization hardness results carry over to this generalized setting. Moreover, we consider the performance of local search strategies on reoptimization problems. We show that local search does not work for solving TSP reoptimization, even in the presence of multiple solutions.
Picture Languages Generated by Assembling Tiles
Authors: Bonizzoni Paola , Ferretti Claudio , Mary A. Roslin Sagaya , Mauri Giancarlo
Published: December 2019

We propose a new formalism for generating picture languages based on an assembly mechanism of tiles that uses rules having a context and a replacement site. More precisely, a picture language will be generated from a finite set of initial pictures by iteratively applying rewriting rules from a given finite set of rules, called a tiling rule system (TRuS system). We prove that the TRuS systems have a greater generative capacity than the tiling systems of Giammarresi and Restivo. This is due mainly to the use of the notion of replacement site, but we further characterize the difference between these systems by comparing them to Wang systems.
State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata
Authors: Kunc Michal , Okhotin Alexander
Published: December 2019

The number of states in a two-way nondeterministic finite automaton (2NFA) needed to represent intersection of languages given by an m-state 2NFA and an n-state 2NFA is shown to be at least m+n and at most m+n+1. For the union operation, the number of states is exactly m+n. The lower bound is established for languages over a one-letter alphabet. The key point of the argument is the following number-theoretic lemma: for all m, n ≥ 2 with m, n ≠ 6 (and with finitely many other exceptions), there exist partitions m = p1 +. . .+ pk and n = q1 +. . .+ql, where all numbers p1, . . . , pk, q1, . . . , ql ≥ 2 are powers of pairwise distinct primes. For completeness, an analogous statement about partitions of any two numbers m, n ∉ {4, 6} (with a few more exceptions) into sums of pairwise distinct primes is established as well.
On Restricted Bio-Turing Machines
Authors: Raghavan Rama , Ramesh H. , Gheorghe Marian , Krishna Shankara Narayanan
Published: December 2019

Here we continue the study of bio-Turing machines introduced in [2] and further investigated in [17]. We introduce a restricted model of bio-Turing machine and we investigate its computational power, a hierarchy of languages accepted, and deterministic and nondeterministic variants. A comprehensive example illustrating the modelling power of the introduced machine ends the paper.
On Almost-Sure Properties of Probabilistic Discrete Event Systems
Authors: Yen Hsu-Chun
Published: December 2019

Although randomization often increases the degree of flexibility in system design, analyzing system properties in the probabilistic framework introduces additional difficulties and challenges in comparison with their nonprobabilistic counterparts. In this paper, we focus on probabilistic versions of two problems frequently encountered in discrete event systems, namely, the reachability and forbidden-state problems. Our main concern is to see whether there exists a (or for every) non-blocking or fair control policy under which a given finite- or infinite-state system can be guided to reach (or avoid) a set of goal states with probability one. For finite-state systems, we devise algorithmic approaches which result in polynomial time solutions to the two problems. For infinite-state systems modelled as Petri nets, the problems are undecidable in general. For the class of persistent Petri nets, we establish a valuation approach through which the convergence behavior of a system is characterized, which in turn yields solutions to the reachability and forbidden-state problems.
Infinite Traces and Symbolic Dynamics - the Minimal Shift Case
Authors: Foryś Wit , Oprocha Piotr
Published: December 2019

We study interrelations between symbolic descriptions of concurrently evolving systems and underlying sequential dynamics. The basic framework for this research is formulated on the background of the theory of traces. We focus our interests on minimal shifts and t-shifts generated by them, that is shifts defined in the space of infinite real traces. We show that sets of infinite real traces generated by minimal shifts are always closed and, under some conditions, are also t-shifts. Additional discussion for the case of small alphabets (containing at most four letters) is also provided.
Weighted Extended Tree Transducers
Authors: Fülöp Zoltán , Maletti Andreas , Vogler Heiko
Published: December 2019

Weighted extended tree transducers (wxtts) over countably complete semirings are systematically explored. It is proved that the extension in the left-hand sides of a wxtt can be simulated by the inverse of a linear and nondeleting tree homomorphism. In addition, a characterization of the class of weighted tree transformations computable by bottom-up wxtts in terms of bimorphisms is provided. Backward and forward application to recognizable weighted tree languages are standard operations for wxtts. It is shown that the backward application of a linear wxtt preserves recognizability and that the domain of an arbitrary bottom-up wxtt is recognizable. Examples demonstrate that neither backward nor forward application of arbitrary wxtts preserves recognizability. Finally, a HASSE diagram relates most of the important subclasses of weighted tree transformations computable by wxtts.
A Nonmonotonic Soft Concurrent Constraint Language to Model the Negotiation Process
Authors: Bistarelli Stefano , Santini Francesco
Published: December 2019

We present an extension of the Soft Concurrent Constraint language that allows the non-monotonic evolution of the constraint store. To accomplish this, we introduce some new operations: retract(c) reduces the current store by c, updateX(c) transactionally relaxes all the constraints of the store that deal with the variables in the set X, and then adds a constraint c; nask(c) tests if c is not entailed by the store. The new retraction operators also permit to reason about Belief Revision, i.e. the process of changing beliefs to take into account a new piece of information. We present this framework as a possible solution to the negotiation of resources (e.g. web services and network resource allocation) that need a given Quality of Service (QoS). For this reason we also show the the new operators of the language satisfy the Belief Revision postulates [20], which can be used in the negotiation process. The QoS requirements (expressed as semiring levels) of all the parties should converge on a formal agreement through a negotiation process, which specifies the contract that must be enforced.
Properties Complementary to Program Self-Reference
Authors: Case John , Moelius III Samuel E.
Published: December 2019

In computability theory, program self-reference is formalized by the not-necessarily-constructive form of Kleene's Recursion Theorem (krt). In a programming system in which krt holds, for any preassigned, algorithmic task, there exists a program that, in a sense, creates a copy of itself, and then performs that task using the self-copy. Interpreted in this way, such self-copying programs have usable self-knowledge. Herein, properties complementary to krt are considered. Of particular interest are those properties involving the implementation of control structures. One main result is that no property involving the implementation of denotational control structures is complementary to krt. This is in contrast to a result of Royer, which showed that implementation of if-then-else — a denotational control structure — is complementary to the constructive form of Kleene's Recursion Theorem. Examples of non-denotational control structures whose implementation is complementary to krt are then given. Some such control structures so nearly resemble denotational control structures that they might be called quasi-denotational.
Self-Indexed Grammar-Based Compression
Authors: Claude Francisco , Navarro Gonzalo
Published: December 2019

Self-indexes aim at representing text collections in a compressed format that allows extracting arbitrary portions and also offers indexed searching on the collection. Current self-indexes are unable of fully exploiting the redundancy of highly repetitive text collections that arise in several applications. Grammar-based compression is well suited to exploit such repetitiveness. We introduce the first grammar-based self-index. It builds on Straight-Line Programs (SLPs), a rather general kind of context-free grammars. If an SLP of n rules represents a text T[1, u], then an SLP-compressed representation of T requires 2n log2 n bits. For that same SLP, our self-index takes O(n log n) + n log2 u bits. It extracts any text substring of length m in time O((m + h) log n), and finds occ occurrences of a pattern string of length m in time O((m(m + h) + h occ) log n), where h is the height of the parse tree of the SLP. No previous grammar representation had achieved o(n) search time. As byproducts we introduce (i) a representation of SLPs that takes 2n log2 n(1 + o(1)) bits and efficiently supports more operations than a plain array of rules; (ii) a representation for binary relations with labels supporting various extended queries; (iii) a generalization of our self-index to grammar compressors that reduce T to a sequence of terminals and nonterminals, such as Re-Pair and LZ78.
Reduction Techniques for Acyclic Cover Transducers
Authors: Champarnaud Jean-Marc , Farré Jacques , Guingne Franck
Published: December 2019

Finite languages and finite subsequential functions can be represented by possibly cyclic finite machines, respectively called cover automata and cover transducers. Reduced cover machines can have fewer states than the corresponding minimal machines, yielding a compact representation for lexicons or dictionaries. We present here a new algorithm for reducing the number of states of an acyclic transducer.
Mop: An Efficient Algorithm for Mining Frequent Pattern with Subtree Traversing
Authors: Deng Zhi-Hong , Gao Ning , Xu Xiao-Ran
Published: December 2019

Mining frequent patterns in database has emerged as an important task in knowledge discovery and data mining. In this paper, we present an efficient algorithm called Mop for fast frequent pattern discovery. Mop utilizes a new kind of data structure called OP_tree (ordered pattern tree) and some particular properties of frequent patterns to facilitate the process of mining frequent patterns. An OP_tree is a special frequent pattern tree, where the children of any node are sorted according to the supports of corresponding items. Efficiency of Mop is achieved with three techniques: (1) it adopts OP_tree to store a large database to avoid repetitive database scans, (2) it finds all frequent 2-patterns in the construction of OP_tree to avoid the costly generation of a large number of candidate 2-patterns, (3) the supports of candidate k-patterns (k>2) can be obtained by traversing a few of specific subtrees of the OP_tree, which greatly reduces the search space and avoid multi-scans of a database. We experimentally compare our algorithm with the Apriori algorithm and the FP-growth algorithm on one real database and one synthetical database. The experimental results show that Mop is about an order of magnitude faster than the Apriori algorithm. Mop also outperforms the FP-growth algorithm, especially when support threshold is very low and databases are quite large.
Efficient Algorithms for Games Played on Trees with Back-edges
Authors: Gandhi Aniruddh , Khoussainov Bakhadyr , Liu Jiamou
Published: December 2019

This paper studies algorithms for deciding the winners of two-player games played on directed graphs. We focus on the case when the underlying graphs are trees with back-edges and provide both theoretical and experimental analysis of this class of games. In particular, we present an algorithm that solves Büchi games played on trees with back-edges in time O(min{r·m, l+m}) where m is the number of edges, l is the sum of the distances from the root to all leaves and the parameter r is bounded by the height of the tree. We also show that parity games played on trees with back-edges can be solved in time O(l + m).
Spiking Neural dP Systems
Authors: Ionescu Mihai , Păun Gheorghe , Pérez-Jiménez Mario J. , Yokomori Takashi
Published: December 2019

We bring together two topics recently introduced in membrane computing, the much investigated spiking neural P systems (in short, SN P systems), inspired from the way the neurons communicate through spikes, and the dP systems (distributed P systems, with components which “read” strings from the environment and then cooperate in accepting their concatenation). The goal is to introduce SN dP systems, and to this aim we first introduce SN P systems with the possibility to input, at their request, spikes from the environment; this is done by so-called request rules. A preliminary investigation of the obtained SN dP systems (they can also be called automata) is carried out. As expected, request rules are useful, while the distribution in terms of dP systems can handle languages which cannot be generated by usual SN P systems. We always work with extended SN P systems; the non-extended case, as well as several other natural questions remain open.
Computing k-block Morphisms by Spiking Neural P Systems
Authors: Nishida Taishin Yasunobu
Published: December 2019

In this paper we show that for every k-block morphism (k ≥ 2) there is a spiking neural P system which computes the morphism. This result generalises the result explored by G. Păun, M. Pérez-Jiménez, and G. Rozenberg. We give an algorithm which constructs the spiking neural P system, that is, if a k-block morphism is given as an input, the algorithm makes rules of the spiking neural P system which computes the morphism.
On the Size of Unary Probabilistic and Nondeterministic Automata
Authors: Bianchi Maria Paola , Mereghetti Carlo , Palano Beatrice , Pighizzini Giovanni
Published: December 2019

We investigate and compare the descriptional power of unary probabilistic and nondeterministic automata (pfa's and nfa's, respectively). We show the existence of a family of languages hard for pfa's in the following sense: For any positive integer d, there exists a unary d-cyclic language such that any pfa accepting it requires d states, as the smallest deterministic automaton. On the other hand, we prove that there exist infinitely many languages having pfa's which from one side do not match a known optimal state lower bound and, on the other side, they are smaller than nfa's which, in turn, are smaller than deterministic automata.
On Networks of Evolutionary Processors with Filters Accepted by Two-State-Automata
Authors: Dassow Jürgen , Truthe Bianca
Published: December 2019

In this paper, we study networks of evolutionary processors where the filters are chosen as special regular sets. We consider networks where all the filters belong to a set of languages that are accepted by deterministic finite automata with a fixed number of states. We show that if the number of states is bounded by two, then every recursively enumerable language can be generated by such a network. If the number of states is bounded by one, then not all regular languages but non-context-free languages can be generated.
Versatility of ‘Continuations’ in Discourse Semantics
Authors: Dinu Anca
Published: December 2019

We show in this paper how the computer science concept of ‘continuations’, together with categorial grammars and a type shifting mechanism, is able to account for a wide range of natural language semantic phenomena, such as hierarchical discourse structure, ellipses, accommodation and free-focus and bound-focus anaphora. The merit of continuations in the dynamic semantics framework is that they abstract away from assignment functions that are essential to the formulations of Dynamic Intensional Logic, Dynamic Montague Grammar, Dynamic Predicate Logic and Discourse Representation Theory, Thus, continuation style semantic do not pose problems such as the destructive assignment problem in Dynamic Predicate Logic or the variable clash problem in Discourse Representation Theory. We argue that continuations are a versatile and powerful tool, particularly well suited to manipulate scope and long distance dependencies, phenomena that abound in natural language semantics.
Solving the International Timetabling Competition: a Deterministic Approach
Authors: Chávez-Bosquez Oscar , Pozos-Parra Pilar , Lengyel Florian
Published: December 2019

The Course Timetabling Problem consists of the weekly scheduling of lectures of a collection of university courses, subject to certain constraints. The International Timetabling Competitions, ITC-2002 and ITC-2007, have been organized with the aim of creating a common formulation for comparison of solution proposals. This paper discusses the design and implementation of an extendable family of sorting-based mechanisms, called Sort Then Fix (STF) algorithms. ITC-2002 and ITC-2007 Post Enrolment based Course Timetabling problem instances were used in this study. The STF approach is deterministic, and does not require swapping or backtracking. Almost all solutions run in less than 10% of the ITC-2002 and less than 2% of the ITC-2007 benchmark times, respectively.
Nested Preferences in Answer Set Programming
Authors: Confalonieri Roberto , Nieves Juan Carlos
Published: December 2019

In this paper, we define a class of nested logic programs, called Nested Logic Programs with Ordered Disjunction (LPODs+), which makes it possible to specify conditional (qualitative) preferences by means of nested preference statements. To this end, we augment the syntax of Logic Programs with Ordered Disjunction (LPODs) to capture more general expressions. We define the LPODs+ semantics in a simple way and we extend most of the results of LPODs showing how our approach generalizes the LPODs framework in a proper way. We also show how the LPODs+ semantics can be computed in terms of a translation procedure that maps a nested ordered disjunction program (OD+-program) into a disjunctive logic program.
A Possibilistic Argumentation Decision Making Framework with Default Reasoning
Authors: Nieves Juan Carlos , Confalonieri Roberto
Published: December 2019

In this paper, we introduce a possibilistic argumentation-based decision making framework which is able to capture uncertain information and exceptions/defaults. In particular, we define the concept of a possibilistic decision making framework which is based on a possibilistic default theory, a set of decisions and a set of prioritized goals. This set of goals captures user preferences related to the achievement of a particular state in a decision making problem. By considering the inference of the possibilistic well-founded semantics, the concept of argument with respect to a decision is defined. This argument captures the feasibility of reaching a goal by applying a decision in a given context. The inference in the argumentation decision making framework is based on basic argumentation semantics. Since some basic argumentation semantics can infer more than one possible scenario of a possibilistic decision making problem, we define some criteria for selecting potential solutions of the problem.
A Threshold for a Polynomial Solution of #2SAT
Authors: De Ita Guillermo , Marcial-Romero J. Raymundo , Hernández José Antonio
Published: December 2019

The #SAT problem is a classical #P-complete problem even for monotone, Horn and two conjunctive formulas (the last known as #2SAT). We present a novel branch and bound algorithm to solve the #2SAT problem exactly. Our procedure establishes a new threshold where #2SAT can be computed in polynomial time. We show that for any 2-CF formula F with n variables where #2SAT(F) ≤ p(n), for some polynomial p, #2SAT(F) is computed in polynomial time. This is a new way to measure the degree of difficulty for solving #2SAT and, according to such measure our algorithm allows to determine a boundary between ‘hard’ and ‘easy’ instances of the #2SAT problem.
Armin: Automatic Trance Music Composition using Answer Set Programming
Authors: Everardo Pérez Flavio Omar , Aguilera Ramírez Fernando Antonio
Published: December 2019

The Artificial Intelligence (AI) has taken a leading role in many activities which used to be made “by hand”; one of them is the musical composition. Such task now has another alternative implementation, through the support of software that can compose different musical genres to the point where a computer can compose pieces with some autonomy. This paper proposes Armin, a system dedicated to the electronic trance music composition. Armins aim is to provide a trance music composition to serve as a template or a base audio file, ready to add more instruments in a mastering (remastering) production Additionally, it seeks to enable greater collaboration between a machine and a human, both seen as musical composers.
Efficient Search Methods for Statistical Dependency Rules
Authors: Hämäläinen Wilhelmiina
Published: December 2019

Dependency analysis is one of the central problems in bioinformatics and all empirical science. In genetics, for example, an important problem is to find which gene alleles are mutually dependent or which alleles and diseases are dependent. In ecology, a similar problem is to find dependencies between different species or groups of species. In both cases a classical solution is to consider all pairwise dependencies between single attributes and evaluate the relationships with some statistical measure like the χ2-measure. It is known that the actual dependency structures can involve more attributes, but the existing computational methods are too inefficient for such an exhaustive search. In this paper, we introduce efficient search methods for positive dependencies of the form X → A with typical statistical measures. The efficiency is achieved by a special kind of a branch-and-bound search which also prunes out redundant rules. Redundant attributes are especially harmful in dependency analysis, because they can blur the actual dependencies and even lead to erroneous conclusions. We consider two alternative definitions of redundancy: the classical one and a stricter one. We improve our previous algorithm for searching for the best strictly non-redundant dependency rules and introduce a totally new algorithm for searching for the best classically non-redundant rules. According to our experiments, both algorithms can prune the search space very efficiently, and in practice no minimum frequency thresholds are needed. This is an important benefit, because biological data sets are typically dense, and the alternative search methods would require too large minimum frequency thresholds for any practical purpose.
Unambiguous Functions in Logarithmic Space
Authors: Herman Grzegorz , Soltys Michael
Published: December 2019

We investigate different variants of unambiguity in the context of computing multi-valued functions. We propose a modification to the standard computation models of Turing machines and configuration graphs, which allows for unambiguity-preserving composition. We define a notion of reductions (based on function composition), which allows nondeterminism but controls its level of ambiguity. In light of this framework we establish reductions between different variants of path counting problems. We obtain improvements of results related to inductive counting.
A Graph Grammar Model of the hp Adaptive Three Dimensional Finite Element Method. Part I
Authors: Paszyńska Anna , Grabska Ewa , Paszyński Maciej
Published: December 2019

The first part of our paper presents a composite programmable graph grammar model for the self-adaptive two dimensional hp Finite Element Method algorithms (2D hp-FEM) with mixed triangular and rectangular finite elements. The two dimensional model is a starting point for the three dimensional model of self-adaptive hp-FEM presented in the second part of this paper. A computational mesh is represented by a composite graph. The operations performed over the mesh are expressed by the graph grammar rules. The three dimensional model is based on the extension of the two dimensional model with rectangular finite elements. In the second part of this paper, we conclude the presentation with numerical examples concerning the generation of the optimal mesh for simulation of the Step-and-Flash Imprint Lithography (SFIL).
Reduced-by-matching Graphs: Toward Simplifying Hamiltonian Circuit Problem
Authors: Blazewicz Jacek , Kasprzak Marta
Published: December 2019

The results presented in the paper are threefold. Firstly, a new class of reduced-by-matching directed graphs is defined and its properties studied. The graphs are output from the algorithm which, for a given 1-graph, removes arcs which are unnecessary from the point of view of searching for a Hamiltonian circuit. In the best case, the graph is reduced to a quasi-adjoint graph, what results in polynomial-time solution of the Hamiltonian circuit problem. Secondly, the systematization of several classes of digraphs, known from the literature and referring to directed line graphs, is provided together with the proof of its correctness. Finally, computational experiments are presented in order to verify the effectiveness of the reduction algorithm.
Spearman Permutation Distances and Shannon's Distinguishability
Authors: Bortolussi Luca , Dinu Liviu P. , Sgarro Andrea
Published: December 2019

Spearman distance is a permutation distance which might be used for codes in permutations beside Kendall distance. However, Spearman distance gives rise to a geometry of strings, which is rather unruly from the point of view of error correction and error detection. Special care has to be taken to discriminate between the two notions of codeword distance and codeword distinguishability. This stresses the importance of rejuvenating the latter notion, extending it from Shannon's zero-error information theory to the more general setting of metric string distances.
Development of Near Sets Within the Framework of Axiomatic Fuzzy Sets
Authors: Wang Lidong , Ren Yan , Liu Xiaodong
Published: December 2019

Near sets result from a generalization of rough sets, which introduced by Peters in 2006, and later formally defined in 2007. Near set theory provides a new framework for representation of objects characterized by the features that describe them. AFS (Axiomatic Fuzzy Set) theory was proposed by Liu (1998), which is a semantic methodology relating to the fuzzy theory. In this paper, a new version of near sets based on AFS theory is established, in which every object has an AFS fuzzy description with definitely semantics. The proposed approach to assessing the nearness (closeness) of objects is not defined directly using a distance metric, but depend on similarity of their fuzzy descriptions. It is also a natural linguistic description that is similar to humans perception. Moreover, an approach to set approximation based on the union of families of objects with similar fuzzy descriptions is given. The near sets based on AFS theory can be viewed as a new development of near sets within the fuzzy context.
Tabular Expressions Operators
Authors: Bourguiba Imen , Moa Belaid
Published: December 2019

Tabular expressions are one of the most important table-based techniques used to formally specify software requirements. The power of tabular expressions stems from their visual structure, and concise representation of mathematical functions and relations. Towards using tabular expressions as a programming language, we propose a tabular expression language in which tabular expressions are first class citizens. The language is built upon atomic tabular expressions and operators. As such, tabular expressions are viewed as a stack of atomic expressions and operators that we apply on them. This view enhances building tools supporting the semantics of tabular expressions, and using them directly during the implementation. The tabular operators introduced are used to compose and decompose tabular expressions in a modular way, which improves their semantics.
Mining Induced/Embedded Subtrees using the Level of Embedding Constraint
Authors: Tan Henry , Hadzic Fedja , Dillon Tharam S.
Published: December 2019

The increasing need for representing information through more complex structures where semantics and relationships among data objects can be more easily expressed has resulted in many semi-structured data sources. Structure comparison among semi-structured data objects can often reveal valuable information, and hence tree mining has gained a considerable amount of interest in areas such as XML mining, Bioinformatics, Web mining etc. We are primarily concerned with the task of mining frequent ordered induced and embedded subtrees from a database of rooted ordered labeled trees. Our previous contributions consist of the efficient Tree Model Guided (TMG) candidate enumeration approach for which we developed a mathematical model that provides an estimate of the worst case complexity for embedded subtree mining. This potentially reveals computationally impractical situations where one would be forced to constrain the mining process in some way so that at least some patterns can be discovered. This motivated our strategy of tackling the complexity of mining embedded subtrees by introducing the Level of Embedding constraint. Thus, when it is too costly to mine all frequent embedded subtrees, one can decrease the level of embedding constraint gradually down to 1, from which all the obtained frequent subtrees are induced subtrees. In this paper we develop alternative implementations and propose two algorithms MB3-R and iMB3-R, which achieve better efficiency in terms of time and space. Furthermore, we develop a mathematical model for estimating the worst case complexity for induced subtree mining. It is accompanied with a theoretical analysis of induced-embedded subtree relationships in terms of complexity for frequent subtree mining. Using synthetic and real world data we practically demonstrate the space and time efficiency of our new approach and provide some comparisons to the two well know algorithms for mining induced and embedded subtrees.
Enumeration and Leader Election in Partially Anonymous and Multi-hop Broadcast Networks
Authors: Chalopin Jérémie , Métivier Yves , Morsellino Thomas
Published: December 2019

We address the enumeration and the leader election problems over partially anonymous and multi-hop broadcast networks. We consider an asynchronous communication model where each process broadcasts a message and all its neighbours receive this message after arbitrary and unpredictable time. In this paper, we present necessary conditions that must be satisfied by any graph to solve these problems and we show that these conditions are sufficient by providing an enumeration algorithm on the one hand and a leader election algorithm on the other hand. For both problems, we highlight the importance of the initial knowledge. Considering the enumeration problem, each process only knows the size of the graph and, contrary to related works, the number of its neighbouring processes is unknown. Whereas for the election problem, we show that this combination of knowledge is not sufficient. Our algorithm assumes that each process initially knows a map of the network (without knowing its position in this map). From the complexity viewpoint, our algorithms offer polynomial complexities (memory at each process, number and size of exchanged messages).
CRN Elimination and Substitution Bases for Complexity Classes
Authors: Mazzanti Stefano
Published: December 2019

Function classes closed with respect to substitution and concatenation recursion on notation are characterized as the substitution closure of finite function sets. Consequently, the sets of TC0, NC1 and L computable functions are characterized as the substitution closure of a finite function set.
An Improved Axiomatic Definition of Information Granulation
Authors: Zhu Ping
Published: December 2019

To capture the uncertainty of information or knowledge in information systems, various information granulations, also known as knowledge granulations, have been proposed. Recently, several axiomatic definitions of information granulation have been introduced. In this paper, we try to improve these axiomatic definitions and give a universal construction of information granulation by relating information granulations with a class of functions of multiple variables. We show that the improved axiomatic definition has some concrete information granulations in the literature as instances.
Crisp and Fuzzy Topological Interior and Closure Operators with Inclusion Degree. Theory and Applications
Authors: Fashandi Homa , Peters James F.
Published: December 2019

This article introduces interior and closure operators with inclusion degree considered within a crisp or fuzzy topological framework. First, inclusion degree is introduced in an extension of the interior and closure operators in crisp topology. This idea is then introduced in fuzzy topology by incorporating a relaxed version of fuzzy subsethood. The introduction of inclusion degree leads to a means of dealing with imperfections and small errors, especially in cases such as digital images where boundaries of subsets of an image are not crisp. The properties of the new operators are presented. Applications of the proposed operators are given in terms of rough sets and mathematical morphology.
Some Methodological Remarks Inspired by the Paper “On inner classes” by A. Igarashi and B. Pierce
Authors: Langmaack Hans , Salwicki Andrzej
Published: December 2019

In [14] an axiomatic approach towards the semantics of FJI, Featherweight Java with Inner classes, essentially a subset of the Java-programming language, is presented. In this way the authors contribute to an ambitious project: to give an axiomatic definition of the semantics of programming language Java. At a first glance the approach of reducing Java's semantics to that of FJI seems promising. We are going to show that several questions have been left unanswered. It turns out that the theory how to elaborate or bind types and thus to determine direct superclasses as proposed in [14] has different models. Therefore the suggestion that the formal system of [14] defines the (exactly one) semantics of Java is not justified. We present our contribution to the project showing that it must be attacked from another starting point. Quite frequently one encounters a set of inference rules and a claim that a semantics is defined by the rules. Such a claim should be proved. One should present arguments: 1° that the system has a model and hence it is a consistent system, and 2° that all models are isomorphic. Sometimes such a proposed system contains a rule with a premise which reads: there is no proof of something. One should notice that this is a metatheoretic property. It seems strange to accept a metatheorem as a premise, especially if such a system does not offer any other inference rules which would enable a proof of the premise. We are going to study the system in [14]. We shall show that it has many non-isomorphic models. We present a repair of Igarashi's and Pierce's calculus such that their ideas are preserved as close as possible.
Building Occurrence Nets from Reveals Relations
Authors: Balaguer Sandie , Chatain Thomas , Haar Stefan
Published: December 2019

Occurrence nets are a well known partial order model for the concurrent behavior of Petri nets. The causality and conflict relations between events, which are explicitly represented in occurrence nets, induce logical dependencies between event occurrences: the occurrence of an event e in a run implies that all its causal predecessors also occur, and that no event in conflict with e occurs. But these structural relations do not express all the logical dependencies between event occurrences in maximal runs: in particular, the occurrence of e in any maximal run may imply the occurrence of another event that is not a causal predecessor of e, in that run. The reveals relation has been introduced to express this dependency between two events. Here we generalize the reveals relation to express more general dependencies, involving more than two events, and we introduce ERL logic to express them as boolean formulas. Finally we answer the synthesis problem that arises: given an ERL formula �, is there an occurrence net 𝒩 such that � describes exactly the dependencies between the events of 𝒩?