bluuebunny/crossref_metadata_2025 huggingface dataset:
Efficient String Matching in Huffman Compressed Texts
Authors: Fredriksson Kimmo , Tarhio Jorma
Published: December 2024

We present an efficient algorithm for scanning Huffman compressed texts. The algorithm parses the compressed text in O(n{[log2σ]/b}) time, where n is the size of the compressed text in bytes, σ is the size of the alphabet, and b is a user specified parameter. The method uses a variable size super-alphabet, with an average size of O({b/[H log2σ]}) characters, where H is the entropy of the text. Each super-character is processed in O(1) time. The algorithm uses O(2b) space and O(b2b) preprocessing time. The method can be easily augmented by auxiliary functions, which can e.g. decompress the text or perform pattern matching in the compressed text. We give three example functions: decoding the text in average time O(n{[log2σ]/[Hw]}), where w is the number of bits in a machine word; an Aho-Corasick dictionary matching algorithm, which works in time O(n{[log2σ]/b}+t), where t is the number of occurrences reported; and a shift-or string matching algorithm that works in time O(n{[log2σ]/b}⌈(m+s-1)/w⌉+t), where m is the length of the pattern and s depends on the encoding. The Aho-Corasick algorithm uses an automaton with variable length moves, i.e. it processes variable number of states at each step. The shift-or algorithm makes variable length shifts, effectively also processing variable number of states at each step. The number of states processed in O(1) time is O(b/[H log2σ]). The method can be applied to several other algorithms as well. Finally, we apply the methods to natural language taking the words (vocabulary) as the alphabet. This improves the compression ratio and allows more complex search problems to be solved efficiently. We conclude with some experimental results.
A Timed Linda Language and its Denotational Semantics
Authors: de Boer Frank S. , Gabbrielli Maurizio , Meo Maria C.
Published: December 2024

We introduce a Timed Linda language (T-Linda) which is obtained by a natural timed interpretation of the usual constructs of the Linda model and by adding a simple primitive which allows one to specify time-outs. Parallel execution of processes follows the scheduling policy of interleaving, however maximal parallelism is assumed for actions depending on time. We first define the operational semantics of T-Linda by means of a transition system, then we define a denotational model which is based on timed reactive sequences. The correctness of this model is proved w.r.t. a notion of observables which includes finite traces of actions and input/output pairs.
Super Rough Semantics
Authors: Mani A.
Published: December 2024

In this research a new algebraic semantics of rough set theory including additional meta aspects is proposed. The semantics is based on enhancing the standard rough set theory with notions of 'relative ability of subsets of approximation spaces to approximate'. The eventual algebraic semantics is developed via many deep results in convexity in ordered structures. A new variation of rough set theory, namely 'ill-posed rough set theory' in which it may suffice to know some of the approximations of sets, is eventually introduced.
About Splicing P Systems with One Membrane
Authors: Verlan Sergey , Margenstern Maurice
Published: December 2024

In this article we consider splicing P systems with one membrane. We show that the original definition of splicing P systems is not complete and we propose several variants in order to complete it. We show that the choice of the variant is important and that the computational power of splicing P systems with one membrane directly depends on it.
An Image Hiding Scheme Based on Multi-bit-reference Substitution	Table Using Dynamic Programming Strategy
Authors: Chan Chi-Shiang , Chang Chin-Chen
Published: December 2024

Simple least-significant-bit (LSB) substitution is the most straightforward way to embed the secret image in the host image. Based on the simple LSB substitution, the method using substitution table is proposed to improve the quality of the stego-image. In this paper, we shall bring up a new method that uses the un-embedded host pixel bits to partition the host pixel into different planes. This way, we can derive the optimal substitution table for each plane. By combining the optimal substitution tables, we can obtain the final result that we call the multi-bit-reference substitution table. After transforming the secret data according multi-bit-reference substitution table, we can embed the transformed secret data in the host image so that the host image will be degraded possibly less. The experimental results show that our method leads to good results.
On Winning Conditions of High Borel Complexity in Pushdown	Games
Authors: Finkel Olivier
Published: December 2024

In a recent paper [19, 20] Serre has presented some decidable winning conditions Ω _{A_1▹…▹A_n▹A_{n+1}} of arbitrarily high finite Borel complexity for games on finite graphs or on pushdown graphs.

We answer in this paper several questions which were raised by Serre in [19,20].

We study classes C _n (A), defined in [20], and show that these classes are included in the class of non-ambiguous context free ω-languages. Moreover from the study of a larger class C _n^λ (A) we infer that the complements of languages in C _n (A) are also non-ambiguous context free ω-languages. We conclude the study of classes C _n (A) by showing that they are neither closed under union nor under intersection.

We prove also that there exists pushdown games, equipped with winning conditions in the form Ω _{A_1▹A_2} , where the winning sets are not deterministic context free languages, giving examples of winning sets which are non-deterministic non-ambiguous context free languages, inherently ambiguous context free languages, or even non context free languages.
A New Partial Semantics for Disjunctive Deductive Databases
Authors: Gire Françoise , Plourde Corinne
Published: December 2024

We propose a new partial semantics for disjunctive deductive databases that we call disjunctive well-founded semantics. This semantics extends the classical well-founded semantics of normal databases for disjunctive databases. We give a declarative definition as well as a computational procedure for this new semantics. We prove that, in the case of disjunctive positive databases, i.e. disjunctive databases without negation, the disjunctive well-founded semantics coincides with the intersection of the minimal models.
A Multimodal Logic Approach to Order of Magnitude Qualitative	Reasoning with Comparability and Negligibility Relations
Authors: Burrieza Alfredo , Ojeda-Aciego Manuel
Published: December 2024

Non-classical logics have proven to be an adequate framework to formalize knowledge representation. In this paper we focus on a multimodal approach to formalize order-of-magnitude qualitative reasoning, extending the recently introduced system MQ, by means of a certain notion of negligibility relation which satisfies a number of intuitively plausible properties, as well as a minimal axiom system allowing for interaction among the different qualitative relations. The main aim is to show the completeness of the formal system introduced. Moreover, we consider some definability results and discuss possible directions for further research.
A Genetic Hillclimbing Algorithm for the Optimal Linear	Arrangement Problem
Authors: Poranen Timo
Published: December 2024

The optimal linear arrangement problem is defined as follows: given a graph G, find a linear ordering for the vertices of G on a line such that the sum of the edge lengths is minimized over all orderings. The problem is NP-complete and it has many applications in graph drawing and in VLSI circuit design.

We introduce a genetic hillclimbing algorithm for the optimal linear arrangement problem. We compare the quality of the solutions and running times of our algorithm to those obtained by simulated annealing algorithms. To obtain comparable results, we use a benchmark graph suite for the problem.

Our experiments show that there are graph classes for which the optimal linear arrangement problem can be efficiently approximated using our genetic hillclimbing algorithm but not using simulated annealing based algorithms. For hypercubes, binary trees and bipartite graphs, the solution quality is better and the running times are shorter than with simulated annealing algorithms. Also the average results are better. On the other hand, there also are graph classes for which simulated annealing algorithms work better.
Random Surfer with Back Step
Authors: Sydow Marcin
Published: December 2024

The World Wide Web with its billions of hyperlinked documents is a huge and important resource of information. There is a necessity of filtering this information. Link analysis of the Web graph turned out to be a powerful tool for automatically identifying authoritative documents. One of the best examples is the PageRank algorithm used in Google [1] to rank search results.

In this paper we extend the model underlying the PageRank algorithm by incorporating "back button" usage modeling in order to make the model less simplistic. We explain the existence and uniqueness of the ranking induced by the extended model. We also develop and implement an efficient approximation method for computing the novel ranking and present succesful experimental results made on 80- and 50- million page samples of the real Web.
Bounds for Validation
Authors: Jaworski Wojciech
Published: December 2024

In this paper we derive the bounds for Validation (known also as Hold-Out Estimate and Train-and-Test Method). We present the best possible bound in the case of 0–1 valued loss function. We also provide the tables where the least sample size is calculated that is necessary for obtaining the bound for a given estimation rate and reliability of estimation. For an arbitrary bounded loss function we present the optimal bound approximation with any given accuracy.
Decidability Analysis of Self-Stabilization for Infinite-State	Systems
Authors: Yen Hsu-Chun , Yu Lien-Po
Published: December 2024

For a variety of infinite-state systems, the problem of deciding whether a given system is self-stabilizing or not is investigated from the decidability viewpoint. We develop a unified strategy through which checking self-stabilization is shown to be decidable for lossy vector addition systems with states, one-counter machines, and conflict-free Petri nets. For lossy counter machines and lossy channel systems, in contrast, the self-stabilization problem is shown to be undecidable.
A Novel Index Coding Scheme for Vector Quantization
Authors: Chang Chin-Chen , Chen Guei-Mei , Hu Yu-Chen
Published: December 2024

A novel method for the compression of the index table of vector quantization (VQ) is proposed in this paper. This method is designed based on the observation that neighboring image blocks are highly correlated. In other words, VQ-encoded neighboring image blocks tend to have similar indices if the codebook used in VQ is previously sorted by the principal component analysis technique. According to this characteristic, we find the same or similar indices around the current processing index to process it. In addition, the pre-statistics technique is employed to gather differences that appear most often in the index table. Simulation results indicate that the newly proposed scheme achieves significant reduction of bit rate without losing any image quality by the original VQ encoding.
Spiking Neural P Systems
Authors: Ionescu Mihai , Păun Gheorghe , Yokomori Takashi
Published: December 2024

This paper proposes a way to incorporate the idea of spiking neurons into the area of membrane computing, and to this aim we introduce a class of neural-like P systems which we call spiking neural P systems (in short, SN P systems). In these devices, the time (when the neurons fire and/or spike) plays an essential role. For instance, the result of a computation is the time between the moments when a specified neuron spikes. Seen as number computing devices, SN P systems are shown to be computationally complete (both in the generating and accepting modes, in the latter case also when restricting to deterministic systems). If the number of spikes present in the system is bounded, then the power of SN P systems falls drastically, and we get a characterization of semilinear sets. A series of research topics and open problems are formulated.
Foundations of Paraconsistent Resolution
Authors: Kamide Norihiro
Published: December 2024

An extended first-order predicate sequent calculus PLK with two kinds of negation is introduced as a basis of a new resolution calculus PRC (paraconsistent resolution calculus) for handling the property of paraconsistency. Herbrand theorem, completeness theorem (with respect to a classical-like semantics) and cut-elimination theorem are proved for PLK. The correspondence between PLK and PRC is shown by using a faithful embedding of PLK into the sequent calculus LK for classical logic.
On Problems in Polymorphic Object-Oriented Languages With Self	Types and Matching
Authors: Winter Michael
Published: December 2024

Subtyping is a basic concept in object-oriented languages. It supports subsumption but, unfortunately, it does not support inheritance of binary methods, i.e., methods taking another argument of type Self? – the same type as the object itself. For this reason, a relation, called matching, on recursive object types has been proposed. This relation does not support subsumption but it allows to inherit binary methods. Two different definitions of matching, called F-bounded and higher-order subtyping, have been proposed and discussed. It was shown that the higher-order interpretation has better theoretical properties, i.e., it leads to a reflexive and transitive matching relation. In this paper we concentrate on two problems in languages with self types and matching based on the higher-order interpretation. We show that the flexibility of self types may not allow the programmer to define certain classes and/or methods which are based on constant values. Furthermore, the higher-order interpretation, especially in the context of bounded quantification, is too restrictive. We argue that a language should be based on both versions of matching and a notion of a type This distinguished from the type Self.
An Efficient and Secure Cryptosystem for Encrypting Long	Messages
Authors: Zhong Sheng
Published: December 2024

Traditionally, due to efficiency considerations, when encrypting long messages using an asymmtric cryptosystem, one needs to use a symmetric cryptosystem in addition. To eliminate this requirement, Hwang, Chang, and Hwang introduced an asymmetric cryptosystem for encrypting long messages. However, they did not give any formal proof of the security of this cryptosystem. In this paper, we propose an improved asymmetric cryptosystem for encrypting long messages, which is both efficient and secure. In the aspect of efficiency, our cryptosystem is about twice as fast as the Hwang-Chang-Hwang cryptosystem. In the aspect of security, besides providing an informal analysis, we rigorously show that computing any part of the plaintext message encrypted using our cryptosystem is as hard as breaking the ElGamal cryptosystem, even if all other parts of the message are already known to the adversary.
Surface Properties from N-Views of a Strictly Convex Solid
Authors: Collings Simon , Kozera Ryszard , Noakes Lyle
Published: December 2024

This paper shows that a strictly convex solid under observation by two or more cameras with known extrinsic and intrinsic parameters contains points on its surface calculable in terms of multiple photographic images. In the case of a solid with a C ^1 boundary we can also extract surface orientation at these points, and when the solid has a C ^2 boundary and a known reflectance map, curvature information can also be calculated.
On-line Approximate String Matching in Natural Language
Authors: Fredriksson Kimmo
Published: December 2024

We consider approximate pattern matching in natural language text. We use the words of the text as the alphabet, instead of the characters as in traditional string matching approaches. Hence our pattern consists of a sequence of words. From the algorithmic point of view this has several advantages: (i) the number of words is much less than the number of characters, which in effect means shorter text (less possible matching positions); (ii) the pattern effectively becomes shorter, so bit-parallel techniques become more applicable; (iii) the alphabet size becomes much larger, so the probability that two symbols (in this case, words) match is reduced. We extend several known approximate string matching algorithms for this scenario, allowing k insertions, deletions or substitutions of symbols (natural language words). We further extend the algorithms to allow k' errors inside the pattern symbols (words) as well. The two error thresholds k and k' can be applied simultaneously and independently. Hence we have in effect two alphabets, and perform approximate matching in both levels. From the application point of view the advantage is that the method is flexible, allowing simple solutions to problems that are hard to solve with traditional approaches. Finally, we extend the algorithms to handle multiple patterns at the same time. Depending on the search parameters, we obtain algorithms that run in linear or sublinear time and that perform the optimal number of word comparisons on average, We conclude with experimental results showing that the methods work well in practice.
A Low-complexity Distance for DNA Strings
Authors: Dinu Liviu P. , Sgarro Andrea
Published: December 2024

We exhibit a low-complexity but non-trivial distance between strings to be used in biology. The experimental results we provide were obtained on a standard laptop and, even if preliminary, are quite encouraging.
Event Structures with Disabling/Enabling Relation and Event	Automata
Authors: Pinna G. Michele
Published: December 2024

In recent years the consideration that events in evolutions of concurrent systems can happen with different histories has received ground. In particular the possibility that part of the history can be abstracted away or identified, like in the collective tokens philosophy for Petri Nets, has gained the stage. The various brands of event structures considered in literature are tailored to a fixed interpretation with respect to the history of an event. We investigate the adequateness of event structures with a disabling/enabling relation, to settle a common ground for the history dependent and history independent interpretations, and we establish a relationship between event automata and these notions of event structures.
An Axiomatization of the Token Game Based on Petri Algebras
Authors: Badouel Eric , Chenou Jules , Guillou Goulven
Published: December 2024

The firing rule of Petri nets relies on a residuation operation for the commutative monoid of non negative integers. We identify a class of residuated commutative monoids, called Petri algebras, for which one can mimic the token game of Petri nets to define the behaviour of generalized Petri nets whose flow relations and place contents are valued in such algebraic structures. The sum and its associated residuation capture respectively how resources within places are produced and consumed through the firing of a transition. We show that Petri algebras coincide with the positive cones of lattice-ordered commutative groups and constitute the subvariety of the (duals of) residuated lattices generated by the commutative monoid of non negative integers. We however exhibit a Petri algebra whose corresponding class of nets is strictly more expressive than the class of Petri nets. More precisely, we introduce a class of nets, termed lexicographic Petri nets, that are associated with the positive cones of the lexicographic powers of the additive group of real numbers. This class of nets is universal in the sense that any net associated with some Petri algebra can be simulated by a lexicographic Petri net. All the classical decidable properties of Petri nets however (termination, covering, boundedness, structural boundedness, accessibility, deadlock, liveness ...) are undecidable on the class of lexicographic Petri nets. Finally we turn our attention to bounded nets associated with Petri algebras and show that their dynamics can be reformulated in term of MV-algebras.
Feature Extraction for Dynamic Integration of Classifiers
Authors: Pechenizkiy Mykola , Tsymbal Alexey , Puuronen Seppo , Patterson David
Published: December 2024

Recent research has shown the integration of multiple classifiers to be one of the most important directions in machine learning and data mining. In this paper, we present an algorithm for the dynamic integration of classifiers in the space of extracted features (FEDIC). It is based on the technique of dynamic integration, in which local accuracy estimates are calculated for each base classifier of an ensemble, in the neighborhood of a new instance to be processed. Generally, the whole space of original features is used to find the neighborhood of a new instance for local accuracy estimates in dynamic integration. However, when dynamic integration takes place in high dimensions the search for the neighborhood of a new instance is problematic, since the majority of space is empty and neighbors can in fact be located far from each other. Furthermore, when noisy or irrelevant features are present it is likely that also irrelevant neighbors will be associated with a test instance. In this paper, we propose to use feature extraction in order to cope with the curse of dimensionality in the dynamic integration of classifiers. We consider classical principal component analysis and two eigenvector-based class-conditional feature extraction methods that take into account class information. Experimental results show that, on some data sets, the use of FEDIC leads to significantly higher ensemble accuracies than the use of plain dynamic integration in the space of original features.
Block Prediction Vector Quantization for Grayscale Image	Compression
Authors: Hu Yu-Chen , Lin Chia-Chen , Chi Kang-Liang
Published: December 2024

This paper presents a new image compression scheme based on vector quantization (VQ) that exploits the inter-block and intra-block correlations in grayscale images. The similar block prediction technique is designed to encode the image blocks by their similar neighboring encoded blocks. Besides, two codebooks are used in the proposed scheme to exploit the intra-block correlation within each image block. Experimental results show that the proposed scheme not only provides good image qualities but also cuts down the required bit rates.
An Infinitary Sequent System for the Equational Theory of	*-continuous Action Lattices
Authors: Palka Ewa
Published: December 2024

We present an infinitary logic ACT _ω in the form of a Gentzen-style sequent system, which is equivalent to the equational theory of *-continuous action lattices [9]. We prove the cut-elimination theorem for ACT _ω and, as a consequence, a theorem on the elimination of negative occurrences of *. This shows that ACT _ω is Π^0_1 , whence, by a result of Buszkowski [1], it is Π^0_1 complete.
Pushdown Automata Free of Explicit Nondeterminism and an Infinite	Hierarchy of Context-free Languages
Authors: Bedregal Benjamín René Callejas
Published: December 2024

By explicit nondeterminism degree of a pushdown automata we mean the maximal number of choices in the transitions of the automata. In this paper we will prove that each pushdown automaton has an equivalent pushdown automaton with degree 1 of explicit nondeterminism, which implies that λ-moves in pda are sufficient to simulate nondeterminism. Moreover, from this normal form (i.e. pda with degree 1 of explicit nondeterminism) we can measure the amount of (implicit) nondeterminism. This measure will be used to determine a countable infinite hierarchy of contextfree language subclasses, whose bottom is the class of deterministic context-free languages and the top is the class of context-free languages.
From Unification Compactness to Learnability
Authors: Marciniec Jacek
Published: December 2024

In this paperwe explain how to derive learnability of some classes of categorial languages as a consequence of the a property that have unifiable infinite sets of types, namely unification compactness. At first we present an alternate (with respect to [6]) proof of learnability of rigid languages, that introduces our method. Then we prove learnability of the class of semi-rigid languages, which lies in between (learnable) class of rigid languages and (not learnable) class of optimal (as defined by Kanazawa in [6]) languages.
Three-Phase Lossless Data Hiding Method for the VQ Index Table
Authors: Chang Chin-Chen , Lin Chih-Yang , Hsieh Yi-Pei
Published: December 2024

Hiding Data in a cover image often applies a steganographic technique that makes the stego image appear as similar to the original cover image as possible. Conventional VQ-based (vector quantization) steganographic methods typically involve codeword replacements to hide secret bits. Such replacements may cause serious distortion or a perceptible block effect on the stego image. In this paper, we propose a three-phase steganographic method for the VQ index table. Instead of applying codeword replacements, the proposedmethod uses different coding schemes-SOC, SMVQ, and VQ-to imply the secret bits. The quality of the stego image generated by the proposed method is completely equal to that of the original cover image (i.e., the VQ cover image). Experimental results have shown that the proposed method has the best stego image quality compared with other methods. In addition, the proposed method provides adaptive embedding capacity and compression bit rate according to predefined thresholds.
Classes of Timed Automata and the Undecidability of Universality
Authors: Moura Arnaldo V. , Pinto Guilherme A.
Published: December 2024

Universality for deterministic Timed Büchi Automata (TBA) is PSPACE-complete but becomes highly undecidable when unrestricted nondeterminism is allowed. More precisely, universality for nondeterministic TBA is Π ^1_1 -hard and its precise position in the analytical hierarchy is still an open question. In this paper we introduce two types of syntactical restrictions to nondeterministic TBA, which are of independent interest, and show that their universality problem is Π ^1_1 -complete. These restrictions define, as we prove, proper subclasses of the class of timed languages defined by nondeterministic TBA. This suggests, as we argue, that no solution to that open question will come without surprise. We also establish closure properties and the relationships between the classes of languages we describe.
Computational Efficiency of Intermolecular Gene Assembly
Authors: Ishdorj Tseren-Onolt , Loos Remco , Petre Ion
Published: December 2024

We investigate here the computational efficiency of gene rearrangement found in ciliates (unicellular organisms). We show how the so-called guided recombination systems, which model this gene rearrangement, can be used as problem solvers. Specifically, these systems can uniformly solve SAT with time complexity O(n ˙ m) for a Boolean formula of m clauses over n variables.
A Semantic Analysis of a Logic for Pragmatics with Assertions,	Obligations, and Causal Implication
Authors: Ranalter Kurt
Published: December 2024

One of the aims of a logic for pragmatics is to provide a logical framework that formalizes reasoning about speech acts. In this paper we investigate the semantics of a fragment of the logic for pragmatics proposed by Bellin and Dalla Pozza in "A pragmatic interpretation of substructural logics" (Feferman Festschrift, ASL Lecture Notes in Logic 15, 2002). The logic deals with acts of assertion and acts of obligation, and it incorporates a rule that relates acts of obligation to acts of assertion via a notion of causal implication. As our main result we show that the logic is sound and complete with respect to a class of algebraic, Kripke, and categorical models.
Algorithmic Logic + SpecVer = the Methodology for High	Integrity Programming − Invited Paper
Authors: Mirkowska Grażyna , Salwicki Andrzej , Swida Oskar
Published: December 2024

Our aim is to present a methodology that integrates all phases of software¡¯s production beginning from the specification phase, through the phase of programming and finally the phase of verification of program against its specification. The theoretical background of the methodology is algorithmic logic [8]. The environment for practical activities of this software project is a plugin SpecVer [11] extending the Eclipse development platform [2].
Petri Net Controlled Finite Automata
Authors: Farwer Berndt , Jantzen Matthias , Kudlek Manfred , Rölke Heiko , Zetzsche Georg
Published: December 2024

We present a generalization of finite automata using Petri nets as control, called Concurrent Finite Automata for short. Several modes of acceptance, defined by final markings of the Petri net, are introduced, and their equivalence is shown. The class of languages obtained by –free concurrent finite automata contains both the class of regular sets and the class of Petri net languages defined by final marking, and is contained in the class of context-sensitive languages.
Optimization in Discovery of Compound Granules
Authors: Jankowski Andrzej , Peters James F. , Skowron Andrzej , Stepaniuk Jaroslaw
Published: December 2024

The problem considered in this paper is the evaluation of perception as a means of optimizing various tasks. The solution to this problem hearkens back to early research on rough set theory and approximation. For example, in 1982, Ewa Orłowska observed that approximation spaces serve as a formal counterpart of perception. In this paper, the evaluation of perception is at the level of approximation spaces. The quality of an approximation space relative to a given approximated set of objects is a function of the description length of an approximation of the set of objects and the approximation quality of this set. In granular computing (GC), the focus is on discovering granules satisfying selected criteria. These criteria take inspiration from the minimal description length (MDL) principle proposed by Jorma Rissanen in 1983. In this paper, the role of approximation spaces in modeling compound granules satisfying such criteria is discussed. For example, in terms of approximation itself, this paper introduces an approach to function approximation in the context of a reinterpretation of the rough integral originally proposed by Zdzisław Pawlak in 1993. We also discuss some other examples of compound granule discovery problems that are related to compound granules representing process models and models of interaction between processes or approximation of trajectories of processes. All such granules should be discovered from data and domain knowledge. The contribution of this article is a proposed solution approach to evaluating perception that provides a basis for optimizing various tasks related to discovery of compound granules representing rough integrals, process models, their interaction, or approximation of trajectories of discovered models of processes.
On Trace-Expressible Behaviour of Petri Nets
Authors: Jółkowska Joanna , Ochmański Edward
Published: December 2024

We propose a trace-based approach to description behaviours of concurrent systems. First, we define the independency relation induced by arbitrary transition system, forming this way an asynchronous transition system. Then we introduce the notion of traceability of transition systems and study some decision problems, related to computing independency and deciding traceability for basic classes of Petri nets. Main results: traceability is decidable for place/transition nets and undecidable in broader classes of nets – inhibitor, reset and transfer nets.
Linear Properties of Zero-Safe Nets with Debit Tokens
Authors: Köhler-Bußmeier Michael , Kudlek Manfred
Published: December 2024

In this contribution we study an extension of zero-safe nets that allows to model cooperation scenarios. Since zero-safe nets cannot be represented as finite nets in general, we study an extension of the firing rule having a close connection to blind counter automatons and the theory of semi-flows. As a main result we obtain, that a representation can always be given as a finite P/T net – although our firing rule is an extension of the original one – i.e. it preserves all the events that have been allowed before.
SAT-based Unbounded Model Checking of Timed Automata
Authors: Penczek Wojciech , Szreter Maciej
Published: December 2024

We present an improvement to the SAT-based Unbounded Model Checking (UMC, for short) algorithm [13]. Our idea consists in building blocking clauses of literals corresponding not only to propositional variables encoding states, but also to more general subformulas over these variables encoding sets of states. This way our approach alleviates an exponential blow-up in the number of blocking clauses. A hybrid algorithm for verifying Timed Automata is proposed, where the timed part of blocking clauses is computed using Difference Bound Matrices. The optimization results in a considerable reduction in the size and the number of generated blocking clauses, thus improving the overall performance. This is shown on the standard benchmark of Fischer's Mutual Exclusion protocol.
An Algebraic Framework for Defining Random Concurrent Behaviours
Authors: Winkowski Józef
Published: December 2024

The paper is devoted to characterizing systems with random behaviours. The characterization is based on considering systems in terms of their possible runs, called processes, where each process is represented by a pomset in an intrinsic, global time independent way and can possibly be obtained by composing sequentially and in parallel other processes.
Grayscale Image Hiding Based on Modulus Function and Greedy	Method
Authors: Hu Yu-Chen , Tsou Chih-Chiang , Su Bing-Hwang
Published: December 2024

A novel LSB-based image-hiding scheme that embeds secret data into the grayscale cover image is proposed in this paper. Several LSB-based image hiding schemes such as simple LSB substitution technique, optimal LSB substitution technique, greedy LSB substitution technique, modulus LSB substitution technique had been proposed. To provide good image quality of the stego-image while requiring a low computational cost, the greedy method and modulus function are employed in the proposed scheme. According to the results, the proposed scheme provides better image quality of stego-image than the comparative schemes while consuming a low computational cost.
Some Issues on Inner Structure of Information. A Definition of the	Decision Making Problem
Authors: Terlikowski Tomasz
Published: December 2024

We continue the analysis of the notion of information in a two-stage decision process. In the previous work and in the present one, when examining specific concepts and types of information, we achieve a better understanding of mathematical contents of the notion. Only elementary set-theoretical tools are used. All the formalism previously introduced is largely used here; it is shortly recalled here.

We try to formally approach several concepts: uncertainty, measurement and prediction, often applied in decision-making theory. Then, after introducing the notion of independent information, we attempt to formulate a precise definition of what we understand as decision making problem.
Characterizing DNA Bond Shapes Using Trajectories
Authors: Domaratzki Michael
Published: December 2024

We consider the use of DNA trajectories to characterize DNA bond shapes. This is an extension of recent work on the bond-free properties of a language. Using a new definition of bondfreeness, we show that we can increase the types of DNA bond shapes which are expressible. This is motivated by the types of bond shapes frequently found in DNA computing.

We examine the algebraic properties of sets of DNA trajectories. In particular, we consider rotation of trajectories and weakening of the bonding conditions expressed by a set of DNA trajectories. We also consider decidability results for bond-freeness with respect to our definition.
Effective Prediction of Web User Behaviour with User-Level	Models
Authors: Dembczyński Krzysztof , Kotłowski Wojciech , Sydow Marcin
Published: December 2024

The paper concerns the problem of predicting behaviour of web users, based on real historical data which constitutes an important issue in web mining.

The research reported here was conducted while the authors participated in the international ECML/ PKDD 2007 Discovery Challenge competition – Track 1.

The results presented here ended up as the winning solution to the contest.

We describe the contest tasks and the real industrial datasets concerning the recorded behaviour of sample of Polish Web users on which our experiments were performed.

We present the whole extensive experimental process from the data preprocessing phase to exploratory analysis of the data to the experimental comparison and discussion of various prediction models which we examined.

As we explain, our solution has low time and space complexity, scales well with large datasets and, at the same time, produces high-quality results.
The Boolean Closure of Growing Context-Sensitive Languages
Authors: Jurdziński Tomasz
Published: December 2024

The set of growing context-sensitive languages (GCSL) is a naturally defined subclass of context-sensitive languages whose membership problem is solvable in polynomial time. Moreover, growing context-sensitive languages and their deterministic counterpart called Church-Rosser Languages (CRL) complement the Chomsky hierarchy in a natural way [13]. In this paper, closures of GCSL under the boolean operations are investigated. It is shown that there exists an infinite intersection hierarchy for GCSL and CRL, answering an open problem from [2]. Furthermore, the expressive power of the boolean closures of GCSL, CRL, CFL and LOGCFL are compared.
Towards a Formal Semantics for the Process Model of the Taverna	Workbench. Part II
Authors: Sroka Jacek , Hidders Jan
Published: December 2024

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

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

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

This paper is the second of two. In the first one [13] we have defined, explained and discussed fundamental notions for describing Scufl graphs and their semantics. Here, in the second part, we use these notions to define the semantics and show that our definition can be used to prove properties of Scufl graphs.
On Distributed k-Anonymization
Authors: Zhong Sheng
Published: December 2024

When a database owner needs to disclose her data, she can k-anonymize her data to protect the involved individuals' privacy. However, if the data is distributed between two owners, then it is an open question whether the two owners can jointly k-anonymize the union of their data, such that the information suppressed in one owner's data is not revealed to the other owner. In this paper, we study this problemof distributed k-anonymization. We have two major results: First, it is impossible to design an unconditionally private protocol that implements any normal k-anonymization function, where normal k-anonymization functions are a very broad class of k-anonymization functions. Second, we give an efficent protocol that implements a normal k-anonymization function and show that it is private against polynomial-time adversaries. Our results have many potential applications and can be extended to three or more parties.
The peak efficiency of initial antihypertensive therapy of primary open-angle glaucoma considering the factors that reduce adherence to the therapy
Authors:   Pirogov Russian National Research Medical University, Moscow, Russian Federation, Glazko N.G. , Volobueva T.M. ,   Pirogov Russian National Research Medical University, Moscow, Russian Federation, Egorov E.A. ,   Pirogov Russian National Research Medical University, Moscow, Russian Federation
Published: December 2024

Glaucoma treatment is a combined approach including selection of antihypertensive drugs to achieve the target pressure and their regular use
by a patient as per the prescribed regimen. Along with a minimum number of instillations, prostaglandin analogues demonstrate the maximum
hypotensive effect at the start of treatment.
Patient adherence to therapy is a key aspect of successful therapy. However, continuous drug instillation leads to several side effects (such
as dryness, hyperemia, burning sensation, itching, and blurred vision after the drug instillation) induced by exposure of preservatives (i. e., an
ingredient of antihypertensive drops) to the eye surface.
The lack of obvious improvement in the course of the disease, discomfortable use of the drops, side effects, and high cost of the drugs may lead
to non-compliant instillation regimen, treatment refusal or unauthorized therapy change by a patient. Mitigation of the negative drug effect not
only protects the eye surface, but also reduces negative emotions of patients resulted from continuous treatment burden. Successful glaucoma
treatment and preservation of visual functions is possible in case of a harmonious combination of medical, psychological and financial factors
that increase patients' satisfaction and, as a result, functional outcomes of the treatment.
KEYWORDS: initial glaucoma therapy, latanoprost, dorsolamide, glaucoma treatment-associated financial burden, undesirable effects of
glaucoma therapy, adherence to glaucoma therapy.
FOR CITATION: Glazko N.G., Volobueva T.M., Egorov E.A. The peak efficiency of initial antihypertensive therapy of primary open-angle
glaucoma considering the factors that reduce adherence to the therapy. Russian Journal of Clinical Ophthalmology. 2024;24(4):200–205 (in
Russ.). DOI: 10.32364/2311-7729-2024-24-4-6
On the issue of the amnesty for the pregnant and having young children women prisoners from the Gulag: implementation of the Decree of August 26, 1950.
Authors:   E.A. Buketov Karaganda University, Saktaganova Zauresh , Gladysheva Alina ,   E.A. Buketov Karaganda University, Sakabay Tolkynay ,   E.A. Buketov Karaganda University
Published: December 2024

The article examines the implementation of Decree No. 0589/183c of August 26, 1950 on the amnesty of pregnant women and women with young children from the Gulag. This amnesty is considered in the context of previous similar amnesties. A brief overview is given of the state of the Gulag system in the late 1940s and early 1950s, as well as the economic and social situation in the USSR during this period. The stages of implementation of the amnesty, the number and contingent of women released are analyzed. An overview of the interaction of the structures implementing the amnesty is given: the leadership of the camps, the prosecutor's office, and the district departments of the Ministry of Internal Affairs. Based on the reviewed archival materials, conclusions were drawn about changes in the assessment of crimes, from the point of view of their danger to the state: the contingent that was not released by the amnesty were women convicted for the economic crimes, mainly convicted by the Decree of the Presidium of the Supreme Soviet of the USSR of June 4, 1947, while women convicted as members of the families of traitors to the Motherland were given the opportunity to be released. The tasks set by the amnesty of August 26, 1950 were not fully realized due to the difficulties in the interaction of the structures that carried it out. About 5% of the total number of women with young children outside the camp remained in prison.
A Short Survey on Energy Efficiency, Harvesting, and Management for Internet of Things
Authors: S. S KARTHIK , V VIJAYALAKSHMI , G Zayaraz
Published: December 2024

Internet of Things (IoT) is a promising technological advancement comprising tiny sensors, intelligent computing devices, cloud, storage, humans, etc. This fundamental architecture and infrastructure of IoT are constructed using sensors and self-powered devices. Energy efficiency and management are a vital part of this platform for sustainable services and application support. This review article discusses notable energy efficiency, harvesting, and management techniques in IoT. This article aims to provide a short study on the notable methods based on classification. The classification techniques are discussed with the novel methodologies and the summary of classes are provided.
ESPACIO HETEROTÓPICO EN TODO EL CIELO SOBRE LA TIERR A (EL SÍNDROME DE WENDY) (2013), DE ANGÉLICA LIDDELL
Authors:   Universidad de Santiago de Compostela, Loureiro Álvarez Katherine E.
Published: December 2024

El objetivo principal de este trabajo es ofrecer una re-flexión sobre el poder simbólico del espacio en el teatro contemporáneo, a partir de una lectura del componente espacial de Todo el cielo sobre la tierra (El síndrome de Wendy) (2013), de Angélica Liddell, como «espacio heterotópico». A través de la superposición de dos espacios aparente-mente opuestos —la isla de Utøya y la isla ficticia de Nunca Jamás—, Liddell construye una heterotopía que desafía las coordenadas conven-cionales de espacio y tiempo, conforme a las ideas de Michel Foucault. Este enfoque escenográfico permite que el teatro se transforme en un espacio simbólico cargado de significados, donde lo real y lo ficcional se entrelazan para generar una reflexión crítica en el espectador. La obra no busca representar los hechos tal como sucedieron, sino desvelar sus implicaciones, convirtiendo el espacio en un lugar de tensión moral y reflexión social.
SILENCIO, ESTRENAMOS: EL GRAN TEATRO DEL MUNDO BAJO EL ESPÍRITU DEL 12 DE FEBRERO
Authors:   Emeterio Diez Puertas, Diez Puertas Emeterio
Published: December 2024

En 1974, el ministro de Información y Turismo, Pío Ca-banillas, llama a Adolfo Marsillach para que vuelva a TVE, de donde había sido expulsado en 1966. Quiere que escriba, dirija e interprete una nueva serie de televisión. Se trata de que su regreso y la serie sean una declaración de lo que significa el espíritu del 12 febrero. Así se llama a la promesa de apertura del régimen que el presidente de Gobierno, Arias Navarro, realiza ese día en las Cortes. Marsillach rueda una serie posibilista en el contenido y marxista en la forma que llama Silencio, es-trenamos. En ella: 1) hace una anatomía del teatro en el tardofranquismo que tendrá su incidencia en la huelga de los actores de febrero de 1975; 2) adopta una poética brechtiana llena de didactismo democrático; y 3) realiza una autocrítica de cómo la propia serie se ha rodado y de cómo se ha recibido por parte de espectadores y críticos de todas las tendencias: inmovilistas, opusdeístas, reformadores, rupturistas... Este contenido metaficcional, dramatúrgico y metaserial hace de Silencio, estrenamos un programa insólito y un texto ejemplar para narrar la reforma imposible, en aquella coyuntura, del teatro y de ese gran teatro del mundo que es el régimen.