bluuebunny/crossref_metadata_2025 huggingface dataset:
Characterization Results for Time-Varying Codes
Authors: Ţiplea Ferucio , Mäkinen Erkki , Trincă Dragos , Enea Costel
Published: December 2024

Time-varying codes associate variable length code words to letters being encoded depending on their positions in the input string. These codes have been introduced in [8] as a proper extension of L codes. This paper is devoted to a further study of time-varying codes. First, we show that adaptive Huffman encodings are special cases of encodings by time-varying codes. Then, we focus on three kinds of characterization results: characterization results based on decompositions over families of sets of words, a Schützenberger like criterion, and a Sardinas-Patterson like characterization theorem. All of them extend the corresponding characterization results known for classical variable length codes.
Rough Equalities From Posets and Rough Difference Orders
Authors: Mani A.
Published: December 2024

In the initial section of this research paper rough equalities from partially ordered approximation spaces are investigated. Special types of rough equalities are characterized via convex and other types of sets. Extension of these to all types of rough equalities is also indicated. Two new theories of "Rough Difference Order" which are often more general and distinct from that of "Rough Orders" are also developed in the last section by the present author.
Application of Rule Induction and Rough Sets to Verification of	Magnetic Resonance Diagnosis
Authors: Słowiński Krzysztof , Stefanowski Jerzy , Siwiński Dariusz
Published: December 2024

We discuss a process of analysing medical diagnostic data by means of the combined rule induction and rough set approach. The first step of this analysis includes the use of various techniques for discretization of numerical attributes. Rough sets theory is applied to determine attribute importance for the patients' classification. The novel contribution concerns considering two different algorithms inducing either minimum or satisfactory set of decision rules. Verification of classification abilities of these rule sets is extended by an examination of sensitivity and specificity measures. Moreover, a comparative study of these composed approaches against other learning systems is discussed. The approach is illustrated on a medical problem concerning anterior cruciate ligament (ACL) rupture in a knee. The patients are described by attributes coming from anamnesis, MR examinations and verified by arthroscopy. The clinical impact of our research is indicating two attributes (PCL index, age) and their specific values that could support a physician in resigning from performing arthroscopy for some patients.
Trajectory-Based Embedding Relations
Authors: Domaratzki Michael
Published: December 2024

We generalize the embedding order to shuffle on trajectories and examine its properties. We give general characterizations of reflexivity, transitivity, anti-symmetry and other properties of binary relations, and investigate the associated decision problems. We also examine the property of convexity of a language with respect to these generalized embedding relations.
C1 Interpolation with Cumulative Chord Cubics
Authors: Kozera Ryszard , Noakes Lyle
Published: December 2024

Cumulative chord C1 piecewise-cubics, for unparameterized data from regular curves in Rn, are constructed as follows. In the first step derivatives at given ordered interpolation points are estimated from ordinary (non-C1) cumulative chord piecewise-cubics. Then Hermite interpolation is used to generate a C1 piecewise-cubic interpolant. Theoretical estimates of orders of approximation are established, and their sharpness verified through numerical experiments. Good performance of the interpolant is also confirmed experimentally on sparse data.
Dual LDA for Face Recognition
Authors: Skarbek Władysław , Kucharski Krzysztof , Bober Mirosław
Published: December 2024

The complete theory for Fisher and dual discriminant analysis is presented as the background of the novel algorithms. LDA is found as composition of projection onto the singular subspace for within-class normalised data with the projection onto the singular subspace for between-class normalised data. The dual LDA consists of those projections applied in reverse order. The experiments show that using suitable composition of dual LDA transformations gives as least as good results as recent state-of-the-art solutions.
Fast Index Filtering in Vector Approximation File
Authors: Skarbek Władysław , Sikora Thomas , Galinski Grzegorz
Published: December 2024

Several fast filtering attributes are analysed for vector interval (cell) pruning while querying the vector approximation file. Beside distance range, sum and median features their deviation forms are introduced. Range and K-NN queries are considered and appropriate acceptance intervals are designed. The impact of feature space dimensionality on index design is discussed, too.
Behaviour and Instantiation of High-Level Petri Net	Processes
Authors: Ehrig Hartmut
Published: December 2024

Processes for high-level nets are often defined as processes of the low-level net Flat(n) which is obtained from N via the well-known flattening construction. This low-level notion of processes for high-level nets, however, is not really adequate, because the high-level structure is completely lost. For this reason we have introduced in a previous paper a new notion of high-level net processes for high-level nets which captures the high-level structure. The key notion is a high-level occurrence net K, which generalizes the well-known notion of occurrence nets from low-level to high-level nets. In contrast to the low-level case we consider high-level occurrence nets together with a set of initial markings of the input places.

In this paper we show under which conditions the behavior of low-level occurrence nets and processes can be generalized to the high-level case. A key notion is the instantiation L of a high-level occurrence net K, where L is a low-level subnet of the flattening Flat(K) with isomorphic net structures of L and K. One of our main results characterizes under which conditions a high-level occurrence net - and hence a high-level net process - has unique and nonoverlapping instantiations and can be represented by the union of all its instantiations.
Real Recursive Functions and Baire Classes
Authors: Mycka Jerzy
Published: December 2024

Recursive functions over the reals [6] have been considered, first as a model of analog computation, and second to obtain analog characterizations of classical computational complexity classes [2].

However, one of the operators introduced in the seminal paper by Cris Moore (in 1996), the minimalization operator, creates some difficulties: (a) although differential recursion (the analog counterpart of classical recurrence) is, to some extent, directly implementable in the General Purpose Analog Computer of Claude Shannon, analog minimalization is far from physical realizability, and (b) analog minimalization was borrowed from classical recursion theory and does not fit well the analytic realm of analog computation. In this paper we use the most natural operator captured from Analysis - the operator of taking a limit - instead of the minimalization with respect to the equivalance of these operators given in [8].

In this context the natural question about coincidence between real recursive functions and Baire classes arises. To solve this problem the limit hierarchy of real recursive funcions is introduced. Relations between Baire classes, effective Baire classes and the limit hierachy are also studied.
Incidence Calculus on Łukasiewicz's Three-valued	Logic
Authors: Qi Guilin , Milligan Peter , Sage Paul
Published: December 2024

Incidence calculus is a probabilistic logic which possesses both numerical and symbolic approaches. However, Liu in [5] pointed out that the original incidence calculus had some drawbacks and she established a generalized incidence calculus theory (GICT) based on Łukasiewicz's three-valued logic to improve it. In a GICT, an incidence function is defined to relate each proposition ϕ in the axioms of the theory to a set of possible worlds in which ϕ has truth value true. But the incidence function only represents those absolute true states of propositions, so it can not deal with the uncertain states. In this paper, we use two incidence functions i _* and i ^* to relate the axioms to the sets of possible worlds. For an axiom ϕ, i _* (ϕ) is to be thought of as the set of possible worlds in which ϕ has truth value true, while i ^* (ϕ) is the set of possible worlds in which ϕ is true or undeterminable. Since i ^* can represent the undeterminable state, our newly defined theory is more efficient to handle vague information than GICT.
Eliptic Curve Based Threshold Proxy Signature Scheme with Known	Signers
Authors: Pomykała Jacek , Barabasz Sławomir
Published: December 2024

In the article we present a new (t,n) threshold proxy signature scheme with known signers. It is based on the elliptic curve cryptosystem whose security refers to the discrete logarithm problem (DLP) in the group E(E _p ) of rational points of elliptic curve over the finite field. In comparision to similar schemes based on the RSA or DSS systems our solution requires application of significantly shorter cryptographic keys. The scheme is relatively simple in construction, has the property of unforgeability, non-repudation and admits the proactive security.
On minimal models of the Region Connection Calculus
Authors: Xia Lirong , Li Sanjiang
Published: December 2024

Region Connection Calculus (RCC) is one primary formalism of qualitative spatial reasoning. Standard RCC models are continuous ones where each region is infinitely divisible. This contrasts sharply with the predominant use of finite, discrete models in applications. In a recent paper, Li et al. (2004) initiate a study of countable models that can be constructed step by step from finite models. Of course, some basic problems are left unsolved, for example, how many non-isomorphic countable RCC models are there? This paper investigates these problems and obtains the following results: (i) the exotic RCC model described by Gotts (1996) is isomorphic to the minimal model given by Li and Ying (2004); (ii) there are continuum many non-isomorphic minimal RCC models, where a model is minimal if it can be isomorphically embedded in each RCC model.
The Weighted Suffix Tree: An Efficient Data Structure for Handling	Molecular Weighted Sequences and its Applications
Authors: Iliopoulos Costas S. , Makris Christos , Panagis Yannis , Perdikuri Katerina , Theodoridis Evangelos , Tsakalidis Athanasios
Published: December 2024

In this paper we introduce the Weighted Suffix Tree, an efficient data structure for computing string regularities in weighted sequences of molecular data. Molecular Weighted Sequences can model important biological processes such as the DNA Assembly Process or the DNA-Protein Binding Process. Thus pattern matching or identification of repeated patterns, in biological weighted sequences is a very important procedure in the translation of gene expression and regulation. We present time and space efficient algorithms for constructing the weighted suffix tree and some applications of the proposed data structure to problems taken from the Molecular Biology area such as pattern matching, repeats discovery, discovery of the longest common subsequence of two weighted sequences and computation of covers.
Exploiting the Lattice of Ideals Representation of a Poset
Authors: De Loof Karel , De Meyer Hans , De Baets Bernard
Published: December 2024

In this paper, we demonstrate how some simple graph counting operations on the ideal lattice representation of a partially ordered set (poset)P allow for the counting of the number of linear extensions of P, for the random generation of a linear extension of P, for the calculation of the rank probabilities for every x∈P, and, finally, for the calculation of the mutual rank probabilities Prob(x>y) for every (x,y)∈P ^2 .

We show that all linear extensions can be counted and a first random linear extension can be generated in O(∣I(P)∣·w(p)) time, while every subsequent random linear extension can be obtained in O(∣P∣·w(P)) time, where ∣I(P)∣ denotes the number of ideals of the poset P and w(P) the width of the poset P. Furthermore, we show that all rank probability distributions can be computed in O(∣I(P)∣·w(P)) time, while the computation of all mutual rank probabilities requires O(∣I(P)∣·∣P∣·w(P)) time, to our knowledge the fastest exact algorithms currently known. It is well known that each of the four problems described above resides in the class of #P-complete counting problems, the counterpart of the NP-complete class for decision problems. Since recent research has indicated that the ideal lattice representation of a poset can be obtained in constant amortized time, the stated time complexity expressions also cover the time needed to construct the ideal lattice representation itself, clearly favouring the use of our approach over the standard ap-proach consisting of the exhaustive enumeration of all linear extensions.
A Robust Content-Based Copy Detection Scheme
Authors: Wu Ming-Ni , Lin Chia-Chen , Chang Chin-Chen
Published: December 2024

Content-based image copy detection can be used as either an alternative approach or a complementary approach to watermarking. To detect copied versions of digital images, which are generated by various image processes, several schemes have been proposed. However, none of them can successfully detect tampering when those images are rotated 90 or 270 degrees from the original image. To solve this problem, we propose a new copy detection scheme based on Y component of image and block strategy. A test image is just converted to a YUV color model where only Y component is used to generate the image signatures. Then, the transformed image is divided into 8×8 blocks. Finally, the relationship between each block and its neighboring eight blocks are recorded by comparing these block's mean values. This image signature generated by our proposed scheme contains the comparative relationship between each block and its neighboring blocks. Our proposed scheme can detect modifications those are generated by 90 or 270 rotation of original one, which can not be detected by Kim's scheme. The optimal block numbers used for image partition have been explored and the efficiency of the proposed scheme is extensively tested with 20,000 test images.
On Simplification of Database Integrity Constraints
Authors: Christiansen Henning , Martinenghi Davide
Published: December 2024

Without proper simplification techniques, database integrity checking can be prohibitively time consuming. Several methods have been developed for producing simplified incremental checks for each update but none until now of sufficient quality and generality for providing a true practical impact, and the present paper is an attempt to fill this gap. On the theoretical side, a general characterization is introduced of the problem of simplification of integrity constraints and a natural definition is given of what it means for a simplification procedure to be ideal. We prove that ideality of simplification is strictly related to query containment; in fact, an ideal simplification pro-cedure can only exist in database languages for which query containment is decidable. However, simplifications that do not qualify as ideal may also be relevant for practical purposes. We present a concrete approach based on transformation operators that apply to integrity constraints written in a rich DATALOG-like language with negation. The resulting procedure produces, at design-time, simplified constraints for parametric transaction patterns, which can then be instantiated and checked for consistency at run-time. These tests take place before the execution of the update, so that only consistency-preserving updates are eventually given to the database. The extension to more expressive languages and the application of the framework to other contexts, such as data integration and concurrent database systems, are also discussed. Our experiments show that the simplifications obtained with our method may give rise to much better performance than with previous methods and that further improvements are achieved by checking consistency before executing the update.
P Systems with Proteins on Membranes
Authors: Păun Andrei , Popa Bianca
Published: December 2024

This work is a continuation of the investigations aiming to bridge membrane computing (where in a compartmental cell-like structure the chemicals to evolve are placed in the compartments defined by the membranes) and brane calculi (where one considers again a compartmental cell-like structure with the chemicals/proteins placed on the membranes themselves). In the current paper we use objects both in compartments and on membranes (the latter are called proteins), with the objects from membranes evolving under the control of the proteins. Several possibilities are considered (objects only moved across membranes or also changed during this operation, with the proteins only assisting the move/change or also changing themselves). Somewhat expected, computational universality is obtained for several combinations of such possibilities.
The Linear Combination of Logistic and Gumbel Random	Variables
Authors: Nadarajah Saralees , Kotz Samuel
Published: December 2024

The exact distribution of the linear combination αX + βY is derived when X and Y are independent logistic and Gumbel random variables. A measure of entropy of the linear combination is investigated. Computer programs are provided for generating tabulations of the percentage points associated with the linear combination. The work is motivated by problems in automation, control, fuzzy sets, neurocomputing and other areas of computer science.
VQ Codebook Searching Algorithm Based on Correlation Property
Authors: Chang Chin-Chen , Lu Tzu-Chuen , Ya Jun-Bin
Published: December 2024

In this paper, we shall present two efficient codebook-matching schemes with a locally adaptive vector quantizer (LAVQ) and a search-ordering coding vector quantizer (SOCVQ) to be applied in the Vector Quantization (VQ) encoding system. The proposed codebook-matching schemes exploit the correlation property between adjacent image blocks so that the process of codebook matching can be speed up. Simulation results show that the time complexity of the proposed schemes is lower than those of PCA, Multipath TSVQ, and DPTSVQ. Moreover, the image quality of the proposed methods is close to those processed by the other methods.
Intercode Regular Languages
Authors: Han Yo-Sub , Salomaa Kai , Wood Derick
Published: December 2024

Intercodes are a generalization of comma-free codes. Using the structural properties of finite-state automata recognizing an intercode we develop a polynomial-time algorithm for determining whether or not a given regular language L is an intercode. If the answer is yes, our algorithm yields also the smallest index k such that L is a k-intercode.

Furthermore, we examine the prime intercode decomposition of intercode regular languages and design an algorithm for the intercode primality test of an intercode recognized by a finite-state automaton. We also propose an algorithm that computes the prime intercode decomposition of an intercode regular language in polynomial time. Finally, we demonstrate that the prime intercode decomposition need not be unique.
Rough set Based Ensemble Classifier forWeb Page Classification
Authors: Saha Suman , Murthy C.A. , Pal Sankar K.
Published: December 2024

Combining the results of a number of individually trained classification systems to obtain a more accurate classifier is a widely used technique in pattern recognition. In this article, we have introduced a rough set based meta classifier to classify web pages. The proposed method consists of two parts. In the first part, the output of every individual classifier is considered for constructing a decision table. In the second part, rough set attribute reduction and rule generation processes are used on the decision table to construct a meta classifier. It has been shown that (1) the performance of the meta classifier is better than the performance of every constituent classifier and, (2) the meta classifier is optimal with respect to a quality measure defined in the article. Experimental studies show that the meta classifier improves accuracy of classification uniformly over some benchmark corpora and beats other ensemble approaches in accuracy by a decisive margin, thus demonstrating the theoretical results. Apart from this, it reduces the CPU load compared to other ensemble classification techniques by removing redundant classifiers from the combination.
Stochastic Petri Box Calculus with Discrete Time
Authors: Tarasyuk Igor V.
Published: December 2024

In the last decades, a number of stochastic enrichments of process algebras was constructed to allow one for specification of stochastic processes within the well-developed framework of algebraic calculi. In [40], a continuous time stochastic extension of finite Petri box calculus (PBC) was proposed called sPBC. The algebra sPBC has interleaving semantics due to the properties of continuous time distributions. At the same time, PBC has step semantics, and it could be natural to propose its concurrent stochastic enrichment. We construct a discrete time stochastic extension dtsPBC of finite PBC. A step operational semantics is defined in terms of labeled transition systems based on action and inaction rules. A denotational semantics is defined in terms of a subclass of labeled discrete time stochastic Petri nets (LDTSPNs) called discrete time stochastic Petri boxes (dts-boxes). A consistency of both semantics is demonstrated. In addition, we define a variety of probabilistic equivalences that allow one to identify stochastic processes with similar behaviour which are differentiated by too strict notion of the semantic equivalence. The interrelations of all the introduced equivalences are investigated.
Fuzzification of Rational and Recognizable Sets
Authors: Konstantinidis Stavros , Nicolae Santean , Yu Sheng
Published: December 2024

In this paper we present a different framework for the study of fuzzy finite machines and their fuzzy languages. Unlike the previous work on fuzzy languages, characterized by fuzzification at the level of their acceptors/generators, here we follow a top-down approach by starting our fuzzification with more abstract entities: monoids and particular families in monoids. Moreover, we replace the unit interval (in fact, a finite subset of the unit interval) as support for fuzzy values with the more general structure of a lattice. We have found that completely distributive complete lattices allow the fuzzification at the highest level, that of recognizable and rational sets. Quite surprisingly, the fuzzification process has not followed thoroughly the classical (crisp) theory. Unlike the case of rational sets, the fuzzification of recognizable sets has revealed a few remarkable exceptions from the crisp theory: for example the difficulty of proving closure properties with respect to complement, meet and inverse morphisms. Nevertheless, we succeeded to prove the McKnight and Kleene theorems for fuzzy sets by making the link between fuzzy rational/recognizable sets on the one hand and fuzzy regular languages and FT-NFA languages (languages defined by NFA with fuzzy transitions) on the other. Finally, we have drawn the attention to fuzzy rational transductions, which have not been studied extensively and which bring in a strong note of applicability.
A Novel Image Hiding Scheme Based on VQ and Hamming Distance
Authors: Chang Chin-Chen , Tai Wei-Liang , Lin Chia-Chen
Published: December 2024

Data hiding is popularly employed in protecting the copyright, secret information and communication secretly with the convenience of network communication. In order to reduce the amount the transmitted data via network, VQ (vector quantization) is applied to compressing the transmitted data. Since VQ is a low-bit-rate compression scheme, it is difficult to find large redundant hiding space and to get stego-images with high quality for hiding data in VQ-based compressed images. A hiding method for VQ-based compressed images is proposed in this paper according to the Hamming distance between the index values of codewords. Our method makes hiding data more effective and provides stego-images with higher quality than other conventional methods. Experimental results demonstrate the effectiveness and the feasibility of our method.
Adaptive Ant Colony Optimization Algorithm Based on Information	Entropy: Foundation and Application
Authors: Li Yancang , Li Wanqing
Published: December 2024

In order to solve the premature convergence problem of the basic Ant Colony Optimization algorithm, a promising modification based on the information entropy is proposed. The main idea is to evaluate stability of the current space of represented solutions using information entropy, which is then applied to turning of the algorithm's parameters. The path selection and evolutional strategy are controlled by the information entropy self-adaptively. Simulation study and performance comparison with other Ant Colony Optimization algorithms and other meta-heuristics on Traveling Salesman Problem show that the improved algorithm, with high efficiency and robustness, appears self -adaptive and can converge at the global optimum with a high probability. The work proposes a more general approach to evolutionary-adaptive algorithms related to the population's entropy and has significance in theory and practice for solving the combinatorial optimization problems.
A Note on the Emptiness of Semigroup Intersections
Authors: Bell Paul
Published: December 2024

We consider decidability questions for the emptiness problem of intersections of matrix semigroups. This problem was studied by A. Markov [7] and more recently by V. Halava and T. Harju [5]. We give slightly strengthened results of their theorems by using a different matrix encoding. In particular, we show that given two finitely generated semigroups of non-singular upper triangular 3 × 3 matrices over the natural numbers, checking the emptiness of their intersections is undecidable. We also show that the problem is undecidable even for unimodular matrices over 3 × 3 rational matrices.
An Algebraic Characterization of the Halting Probability
Authors: Chaitin Gregory
Published: December 2024

Using 1947 work of Post showing that the word problem for semigroups is unsolvable, we explicitly exhibit an algebraic characterization of the bits of the halting probability Ω. Our proof closely follows a 1978 formulation of Post's work by M. Davis. The proof is self-contained and not very complicated.
Foundations of Modal Deductive Databases
Authors: Nguyen Linh Anh
Published: December 2024

We give formulations for modal deductive databases and present a modal query language called MDatalog. We define modal relational algebras and give the seminaive evaluation algorithm, the top-down evaluation algorithm, and the magic-set transformation for MDatalog queries. The results of this paper like soundness and completeness of the top-down evaluation algorithm or correctness of the magic-set transformation are proved for the multimodal logics of belief KDI4 _s 5, KDI45, KD4 _s 5 _s , KD45 _{(m)} , KD4I _g 5 _a , and the class of serial context-free grammar logics. We also show that MDatalog has PTIME data complexity in the logics KDI4 _s 5, KDI45, KD4 _s 5 _s , and KD45 _{(m)} .
How to Compute Times of Random Walks Based Distributed Algorithms
Authors: Bui Alain , Sohier Devan
Published: December 2024

Random walk based distributed algorithms make use of a token that circulates in the system according to a random walk scheme to achieve their goal. To study their efficiency and compare it to one of the deterministic solutions, one is led to compute certain quantities, namely the hitting times and the cover time. Until now, only bounds on these quantities were known.

First, this paper presents two generalizations of the notions of hitting and cover times to weighted graphs. Indeed, the properties of random walks on symmetrically weighted graphs provide interesting results on random walk based distributed algorithms, such as local load balancing. Both of these generalizations are proposed to precisely represent the behaviour of these algorithms, and to take into account what the weights represent.

Then, we propose an algorithm to compute the n^2 hitting times on a weighted graph of n vertices, which we improve to obtain a O( n^3 ) complexity. This complexity is the lowest up to now. This algorithm computes both of the generalizations that we propose for the hitting times on a weighted graph.

Finally, we provide the first algorithm to compute the cover time (in both senses) of a graph. We improve it to achieve a complexity of O( n^32^n ). The algorithms that we present are all robust to a topological change in a limited number of edges. This property allows us to use them on dynamic graphs.
Inference of Parsable Graph Grammars for Syntactic Pattern	Recognition
Authors: Flasiński Mariusz
Published: December 2024

A research into a syntactic pattern recognition model based on (edNLC) graph grammars (introduced and investigated in Janssens and Rozenberg Inform. Sci. 20 (1980), 191-216, and Janssens, Rozenberg and Verraedt Comp. Vis. Graph. Image Process. 18 (1982), 279-304) has resulted in defining the efficient, O(n ^2 ), parsing schemes for the ETPL(k) subclass of these grammars and applying it for scene analysis, CAD/CAMobject analysis and constructingAI systems (Flasiński Patt. Recogn. 21 (1988), 623-629, Flasiński Comp. Vis. Graph. Image Process. 47 (1989), 1-21, Flasiński Patt. Recogn. 26 (1993), 1-16, Flasiński Comp. Aided-Des. 27 (1995), 403-433, Flasiński Theor. Comp. Sci. 201 (1998), 189-231). In the paper the grammatical inference method for the parsable ETPL(k) graph grammars is defined, completing the development of this syntactic pattern recognition model.
Path Languages of Random Permitting Context Tree Grammars are	Regular
Authors: Drewes Frank , van der Merwe Brink
Published: December 2024

The path languages of random permitting context tree languages are investigated. The main result is that these path languages are regular. This confirms a previous conjecture.
WeightedWord Recognition
Authors: Laugerotte Éric , Ziadi Djelloul
Published: December 2024

In this paper, we introduce the notion of Thompson weighted automaton. We show that an ε-free automaton constructed from the Thompson weighted automaton for a regular weighted expression E can be computed in quadratic time on the size of E. Moreover the coefficient of a word u in the noncommutative formal series associated to E, can be computed in time O(∣u∣ × �E∣).
An Edge-based Image Copy Detection Scheme
Authors: Lin Chia-Chen , Wang Shing-Shoung
Published: December 2024

This paper presents a novel scheme to detect copied versions of digital images, particularly in an Internet environment based on edge information of images. The edge information is used to generate the signature set for a corresponding image. The edge-based signature sets are then used to compute the distortions between query images and test images, from among which a user wants to find copies. Experimental results confirm that the proposed scheme not only withstands various modifications of an original image but also offers good detection performance in dealing with various rotations, shifting of 17.5% of the width or height of an image, and cutting out up to 45% of the area of an image, which previous research work has found difficult to detect. Therefore, our proposed scheme could be very helpful in detecting copies of digital images transmitted in an Internet environment.
Rough Rule Extracting From Various Conditions: Incremental and	Approximate Approaches for Inconsistent Data
Authors: Liu Yong , Xu Congfu , Zhang Qiong , Pan Yunhe
Published: December 2024

Rough rule extraction refers to the rule induction method by using rough set theory. Although rough set theory is a powerful mathematical tool in dealing with vagueness and uncertainty in data sets, it is lack of effective rule extracting approach under complex conditions. This paper proposes several algorithms to perform rough rule extraction from data sets with different properties. Firstly, in order to obtain uncertainty rules from inconsistent data, we introduce the concept of confidence factor into the rule extracting process. Then, an improved incremental rule extracting algorithm is proposed based on the analysis of the incremental data categories. Finally, above algorithms are further extended to perform approximate rule extraction from huge data sets. Preliminary experiment results are encouraging.
Fuzzy Symmetry Based Real-Coded Genetic Clustering Technique for	Automatic Pixel Classification in Remote Sensing Imagery
Authors: Saha Sriparna , Bandyopadhyay Sanghamitra
Published: December 2024

The problem of classifying an image into different homogeneous regions is viewed as the task of clustering the pixels in the intensity space. In particular, satellite images contain landcover types some of which cover significantly large areas, while some (e.g., bridges and roads) occupy relatively much smaller regions. Automatically detecting regions or clusters of such widely varying sizes presents a challenging task. In this paper, a newly developed real-coded variable string length genetic fuzzy clustering technique with a new point symmetry distance is used for this purpose. The proposed algorithm is capable of automatically determining the number of segments present in an image. Here assignment of pixels to different clusters is done based on the point symmetry based distance rather than the Euclidean distance. The cluster centers are encoded in the chromosomes, and a newly developed fuzzy point symmetry distance based cluster validity index, FSym-index, is used as a measure of the validity of the corresponding partition. This validity index is able to correctly indicate presence of clusters of different sizes and shapes as long as they are internally symmetrical. The space and time complexities of the proposed algorithm are also derived. The effectiveness of the proposed technique is first demonstrated in identifying two small objects from a large background from an artificially generated image and then in identifying different landcover regions in remote sensing imagery. Results are compared with those obtained using the well known fuzzy C-means algorithm both qualitatively and quantitatively.
Methods as Parameters: A Preprocessing Approach to Higher Order in	Java
Authors: Bellia Marco , Occhiuto M. Eugenia
Published: December 2024

The paper investigates the use of preprocessing in adding higher order functionalities to Java, that is in passing methods to other methods. The approach is based on a mechanism which offers a restricted, disciplined, form of abstraction that is suitable to the integration of high order and object oriented programming. We show how this integration can be exploited in programming through the development of an example. Then, we discuss how the expressive power of the language is improved. A new syntax is introduced for formal and actual parameters, hence the paper defines a translation that, at preprocessing time, maps programs of the extended language into programs of ordinary Java.
Constraint BasedWorld Modeling
Authors: Göhring Daniel , Mellmann Heinrich , Gerasymova Kataryna , Burkhard Hans-Dieter
Published: December 2024

Common approaches for robot navigation use Bayesian filters like particle filters, Kalman filters and their extended forms. We present an alternative and supplementing approach using constraint techniques based on spatial constraints between object positions. This yields several advantages. The robot can choose from a variety of belief functions, and the computational complexity is decreased by efficient algorithms. The paper investigates constraint propagation techniques under the special requirements of navigation tasks. Sensor data are noisy, but a lot of redundancies can be exploited to improve the quality of the result. We introduce two quality measures: The ambiguity measure for constraint sets defines the precision, while inconsistencies are measured by the inconsistency measure. The measures can be used for evaluating the available data and for computing best fitting hypothesis. A constraint propagation algorithm is presented.
A Deterministic Algorithm for Identifying Direct Superclasses in	Java
Authors: Langmaack Hans , Salwicki Andrzej , Warpechowski Marek
Published: December 2024

In an earlier article [5] we analyzed the problem of determining direct superclasses in Java and Java-like languages. We gave a specification of the problem showing that it closely reflects the requirements of [2]. We presented a non-deterministic algorithm and proved its correctness and completeness. This paper presents a deterministic algorithm which elaborates direct superclasses. The new algorithm is better for it presents all details of implementation and its cost seems lower than the cost of the non-deterministic algorithm. Another advantage of the proposed algorithm is error recovery. Should the algorithm report an error it continues its job and possibly reports more errors in one pass.
LDYIS: a Framework for Model Checking Security Protocols
Authors: Lomuscio Alessio , Penczek Wojciech
Published: December 2024

We present a formalism for the automatic verification of security protocols based on multi-agent systems semantics. We give the syntax and semantics of a temporal-epistemic securityspecialised logic and provide a lazy-intruder model for the protocol rules that we argue to be particularly suitable for verification purposes. We exemplify the technique by finding a (known) bug in the traditional NSPK protocol.
Translation of Timed Promela to Timed Automata with Discrete Data
Authors: Nabiałek Wojciech , Janowska Agata , Janowski Paweł
Published: December 2024

The aim of the work is twofold. In order to face the problem of modeling time constraints in Promela, a timed extension of the language is presented. Next, timed Promela is translated to timed automata with discrete data, that is timed automata extended with integer variables. The translation enables verification of Promela specifications via tools accepting timed automata as input, such as VerICS or Uppaal. The translation is illustrated with a well known example of Fischer's mutual exclusion protocol. Some experimental results are also presented.
Processes in Systems with Limited Resources in the Context of	Non-extensive Thermodynamics
Authors: Strzałka Dominik , Grabowski Franciszek
Published: December 2024

This paper presents a preliminary analysis of the system behavior that works far from the thermodynamical equilibrium states in the environment with limited resources. The examples of such systems are the real computer systems. Nowadays in such systems the runoff characteristic of the information flow is very turbulent in contradiction to the current existing laminar models. These systems work under constant overload, which means a permanent thermodynamical non-equilibrium (from the thermodynamical point of view). For such a situation the classical approach to their modeling is still based on Boltzmann-Gibbs (BG) thermodynamics,which is proper only for systems that are in equilibriumstate (sometimes called thermostatic) or very close to it. The changing number of tasks N in such systems and the limited resourcesK of the environment cause its chaotic behavior and generate the dependencies that have got a long-termproperty. Such processes degrade the system performance X and elongate the response time R; in other words degrade the Quality of Service (QoS). To understand the whole behavior of such systems one needs a proper thermodynamical basis that seems to be the Tsallis formula of the non-extensive entropy.
Partial Conway and Iteration Semirings
Authors: Bloom Stephen L. , Ésik Zoltan , Kuich Werner
Published: December 2024

A Conway semiring is a semiring S equipped with a unary operation *: S → S, always called 'star', satisfying the sum star and product star identities. It is known that these identities imply a Kleene type theorem. Some computationally important semirings, such as N or N ^{rat} ≪Σ≫ of rational power series of words on Σ with coefficients in N, cannot have a total star operation satisfying the Conway identities. We introduce here partial Conway semirings, which are semirings S which have a star operation defined only on an ideal of S; when the arguments are appropriate, the operation satisfies the above identities. We develop the general theory of partial Conway semirings and prove a Kleene theorem for this generalization.
Involution Solid and Join codes
Authors: Jonoska Nataša , Kari Lila , Mahalingam Kalpana
Published: December 2024

In this paper we study a generalization of the classical notions of solid codes and commafree codes: involution solid codes (�-solid) and involution join codes (�-join). These notions are motivated by DNA strand design where Watson-Crick complementarity can be formalized as an antimorphic involution. We investigate closure properties of these codes, as well as necessary conditions for �-solid codes to be maximal. We show how the concept of �-join can be utilized such that codes that are not themselves �-comma free can be split into a union of subcodes that are �-comma free.
Modeling the Dance Video Semantics using Regular Tree	Automata
Authors: Ramadoss Balakrishnan , Rajkumar Kannan
Published: December 2024

Dance video is one of the important types of narrative videos with an interesting and semantics-rich content. Modeling the expressive dance semantics is a real challenging task, compared to the other types of videos such as news, sports and video streams. This paper proposes a formal conceptual model based on the theory of regular tree automata called, DanceGrammar. The DanceGrammar and its tree automaton represent the dance pieces that are associated with the accompanying song. A dance piece incorporates many dance video semantics such as dancer objects, actors, dance movements, emotions and spatio-temporal relationships among the dancers and their actors. This paper then outlines the translation rules to convert the tree automaton of the Dance- Grammar into W3C XML Schema and presents the underlying XML Schema representations.
Unsupervised Pixel Classification in Satellite Imagery: A	Two-stage Fuzzy Clustering Approach
Authors: Mukhopadhyay Anirban , Maulik Ujjwal
Published: December 2024

A popular approach for landcover classification in remotely sensed satellite images is clustering the pixels in the spectral domain into several fuzzy partitions. It has been observed that performance of the clustering algorithms deteriorate with more and more overlaps in the data sets. Motivated by this observation, in this article a two-stage fuzzy clustering algorithm is described that utilizes the concept of points having significant membership to multiple classes. The points situated in the overlapped regions of different clusters are first identified and excluded from consideration while clustering. Thereafter, these points are given class labels based on Support vector Machine classifier which is trained by the remaining points. The well known Fuzzy C-Means algorithm and some recently proposed genetic clustering schemes are utilized in the process. The effectiveness of the two-stage clustering technique has been demonstrated on IRS remote sensing satellite images of the cities of Bombay and Calcutta and compared with other well known clustering techniques. Also statistical significance test has been carried out to establish the statistical significance of the clustering results.
The Halting Probability via Wang Tiles
Authors: Chaitin Gregory
Published: December 2024

Using work of Hao Wang, we exhibit a tiling characterization of the bits of the halting probability.
sPBC: A Markovian Extension of Petri Box Calculus with Immediate	Multiactions
Authors: Macià Hermenegilda , Valero Valentín , Cuartero Fernando , Ruiz M. Carmen
Published: December 2024

Petri Box Calculus (PBC) is an algebraicmodel for the description of concurrent systems and sPBC (stochastic Petri Box Calculus) is a Markovian extension of that model. In this paper we add immediate multiactions to sPBC in order to increase the description power of this language. Thus, we both have timed multiactions that follow an exponential distribution, and multiactions that do not require any time and can be immediately executed. The denotational semantics of this model is based on a special class of GSPN (Generalized Stochastic Petri Nets), called gs-boxes.
Algorithmic Approach to Devaney Chaos in Shift Spaces
Authors: Oprocha Piotr
Published: December 2024

Among the class of sofic shifts Devaney chaos is equivalent to topological transitivity. The aim of this paper is to study possibilities of detection of this phenomena when a right-resolving graph presentation of a sofic shift is given. We show that Devaney chaos detection is co-NP-hard problem and point out some possible improvements of algorithms known from the literature.
A Cancellation Theorem for BCCSP
Authors: Aceto Luca , Fokkink Wan , Ingolfsdottir Anna
Published: December 2024

This paper presents a cancellation theorem for the preorders in van Glabbeek's linear time-branching time spectrum over BCCSP. Apart from having some intrinsic interest, the proven cancellation result plays a crucial role in the study of the cover equations, in the sense of Fokkink and Nain, that characterize the studied semantics. The techniques used in the proof of the cancellation theorem may also have some independent interest.
Second Order Fuzzy Measure and Weighted Co-Occurrence Matrix for	Segmentation of Brain MR Images
Authors: Maji Pradipta , Kundu Malay K. , Chanda Bhabatosh
Published: December 2024

A robust thresholding technique is proposed in this paper for segmentation of brain MR images. It is based on the fuzzy thresholding techniques. Its aim is to threshold the gray level histogram of brain MR images by splitting the image histogram into multiple crisp subsets. The histogram of the given image is thresholded according to the similarity between gray levels. The similarity is assessed through a second order fuzzy measure such as fuzzy correlation, fuzzy entropy, and index of fuzziness. To calculate the second order fuzzy measure, a weighted co-occurrence matrix is presented, which extracts the local information more accurately. Two quantitative indices are introduced to determine the multiple thresholds of the given histogram. The effectiveness of the proposed algorithm, along with a comparisonwith standard thresholding techniques, is demonstrated on a set of brain MR images.
Geometric transform Invariant Texture Analysis based on Modified	Zernike Moments
Authors: Vyas Vibha S. , Rege Priti P.
Published: December 2024

In this paper, geometric invariant texture analysis, which comprises of rotation, scale and translation (RST) invariance, is presented. Many types of moments and functions of moments have been utilized in RST invariant pattern recognition applications. However, use of moments for texture content-based image analysis is limited. Here, application of Zernike moment for geometric invariant texture analysis is studied. An algorithm is proposed to design fast and modified Zernike moments to extract a particular texture from image irrespective of its rotation scale change and translation. The algorithm is tested for its robustness in the presences of various noises like salt and paper, Gaussian and speckle noise. The operator is evaluated for computation of moments on different data sets of textures like Brodatz and Vistex. Comparison is done with traditional Zernike moments based techniques, Fast Fourier Transform (FFT)-Zernike moments based technique and proposed modified Zernike moment based technique.