bluuebunny/crossref_metadata_2025 huggingface dataset:
Deriving and Retrieving Contextual Categorical Information through	Instance Inheritance
Authors: Analyti Anastasia , Spyratos Nicolas , Constantopoulos Panos
Published: December 2024

In semantic and object-oriented data models, each class has one or more typing properties that associate it to other classes, and carry type information about all instances of the class. We introduce a new kind of property that we call instance-typing property. An instance-typing property associates an instance of a class to another class, and carries type information about that particular instance (and not about all instances of the class). Instance-typing properties are important as they allow to represent summary information about an instance, in addition to specific information. In this paper, we study inheritance of properties from a class to an instance, using type information about the class, as well as type information about the instance. This kind of inheritance, that we call contextual instance-inheritance, provides us with the most specific type information about the instance, in a particular context. Intuitively, a context is a metaclass of interest with respect to which this most specific information is determined. We demonstrate that contextual instance-inheritance is a powerful conceptual modeling mechanism, capable of expressing valuable information about instances. We also provide a framework in which derived instance-inherited properties can be represented and retrieved in the same way as ``usual'' properties.
The Ground Tree Transducer Game with Identical Tree Automata
Authors: Apró János , Vágvölgyi Sándor
Published: December 2024

We study that version of the ground tree transducer game where the same tree automaton appears as the first and second component of the associated ground tree transducer. We give conditions which imply that Beta has a winning strategy. Furthermore, we show the following decidability result. Given a ground tree transducer game where the underlying tree automaton A cannot evaluate some tree into a state or A is deterministic, we can decide which player has a winning strategy. Moreover, whatever player has a winning strategy, we can effectively construct a partial recursive winning strategy for him.
Decomposing Timed Push Down Automata
Authors: Krishnan Padmanabhan
Published: December 2024

In this paper we define a particular type of timed push down automata. We show that the emptiness problem for this class is decidable. We also present a notion of homomorphism and parallel decomposition for these automata. These notions are a generalisation of the homomorphism and decomposition via partitions for finite automata.
Nonmodularity Results for Lambda Calculus
Authors: Salibra Antonino
Published: December 2024

The variety (equational class) of lambda abstraction algebras was introduced to algebraize the untyped lambda calculus in the same way cylindric and polyadic algebras algebraize the first-order predicate logic. In this paper we prove that the lattice of lambda theories is not modular and that the variety generated by the term algebra of a semi-sensible lambda theory is not congruence modular. Another result of the paper is that the Mal'cev condition for congruence modularity is inconsistent with the lambda theory generated by equating all the unsolvable λ-terms.
The Modal Query Language MDatalog
Authors: Nguyen Linh Anh
Published: December 2024

We propose a modal query language called MDatalog. A rule of an MDatalog program is a universally quantified modal Horn clause. This language is interpreted in fixed-domain first-order modal logics over signatures without functions. We give algorithms to construct the least models for MDatalog programs. We show PTIME complexity of computing queries for a given MDatalog program in the logics KD, T, KB, KDB, B, K5, KD5, K45, KD45, KB5, and S5, provided that the quantifier depths of queries and the program are finitely bounded, and that the modal depth of the program is finitely bounded in the case when the considered logic is not an extension of K5. Some examples are given to illustrate application of the techniques to reason about belief and knowledge.
Prelanguages Versus Submonoids
Authors: Ostravský Jan
Published: December 2024

In [9] submonoids of a commutative monoid are characterized by means of their relations of domination, subgroups of a commutative monoid are characterized by means of their relations of double domination. The main purpose of this paper is to transfer these results to general monoids. The important means will be certain relations, which we shall study in detail.
Geodesy and connectivity in lattices
Authors: Ronse Christian , Serra Jean
Published: December 2024

This paper generalizes the notion of symmetrical neighbourhoods, which have been used to define connectivity in the case of sets, to the wider framework of complete lattices having a sup-generating family. Two versions (weak and strong) of the notion of a symmetrical dilation are introduced, and they are applied to the generation of "connected components" from the so-called "geodesic dilations". It turns out that any "climbing" "weakly symmetrical" extensive dilation induces a "geodesic" connectivity. When the lattice is the one of subsets of a metric space, the connectivities which are obtained in this way may coincide with the usual ones under some conditions, which are clarified. The abstract theory can be applied to grey-level and colour images, without any assumption of translation-invariance of operators.
Supporting Textual Input by Using Multiple Entropy Models
Authors: Bach Joscha
Published: December 2024

The efficiency of textual input of disabled users can be considerably improved by em-ploying prediction methods as they are used in data compression algorithms. In this paper, the application of the PPM algorithm is described along with a technique of utilizing multiple concur-rent prediction models. In a prototypical implementation called PRIS the method has been found to reduce the number of keystrokes necessary to enter textual data by 55 to 62 percent over common text entry. Compared with zero-order prediction as used in most textual input aids that are currently used, PRIS reduces the number of keystrokes between 12 and 24 percent.
Multisequential Grammars with Homogeneous Selectors
Authors: Meduna Aleksander , Vurm Petr
Published: December 2024

This paper deals with selective substitution grammars. It concentrates on multisequential grammars with homogeneous selectors that have all their activated parts identical. The present paper reduces the number and size of selectors in these grammars. Indeed, it demonstrates that for every phrase-structure grammar, there exists an equivalent multisequential grammar having two homogeneous selectors, either of which has only two activated parts.
On the Injectivity of the Parikh Matrix Mapping
Authors: Atanasiu Adrian , Martín-Vide Carlos , Mateescu Alexandru
Published: December 2024

In this paper we investigate the injectivity of the Parikh matrix mapping. This research is done mainly on the binary alphabet. We identify a family of binary words, refered to as ``palindromic amiable'', such that two such words are palindromic amiable if and only if they have the same image by the Parikh matrix mapping. Some other related problems are discussed, too.
PathLog: a Query Language for Schemaless Databases of Partially	Labeled Objects
Authors: Pankowski Tadeusz
Published: December 2024

In the paper we deal with the problem of modeling and querying information in schemaless databases of partially labeled objects (PLO-DB). Partially labeled objects are used for modeling data within repositories integrating both structured and semistructured data. The proposed PLO (Partially Labeled Objects) data model originates from the OEM data model and extends it by allowing partial labeling of objects. For PLO-DB we propose a rule-oriented query language PathLog, which data manipulation paradigm is based on set-theoretical operations and on rules (in Datalog style) involving Skolem functions and referential variables. The main contribution of the paper is the development of a formalized and consistent model of schemaless databases of partially labeled objects and its query language PathLog.
Markov Decision Processes and Deterministic Büchi Automata
Authors: Beauquier Danièle
Published: December 2024

We prove that given a Markov Decision Process (MDP) and a fixed subset of its states~F, there is a Markov policy which maximizes everywhere the probability to reach F infinitely often. Moreover such a maximum policy is computable in polytime in the size of the MDP. This result can be applied in order to control a system with randomized or uncertain behavior with respect to a given property to optimize.
A Modal Logic for Indiscernibility and Complementarity in	Information Systems
Authors: Balbiani Philippe
Published: December 2024

In this paper, we study indiscernibility relations and complementarity relations in information systems. The first-order characterization of indiscernibility and complementarity is obtained through a duality result between information systems and certain structures of relational type characterized by first-order conditions. The modal analysis of indiscernibility and complementarity is performed through a modal logic which modalities correspond to indiscernibility relations and complementarity relations in information systems.
On Average Depth of Decision Trees Implementing Boolean	Functions
Authors: Chikalov Igor
Published: December 2024

The article considers the representation of Boolean functions in the form of decision trees. It presents the bounds on average time complexity of decision trees for all classes of Boolean functions that are closed over substitution, and the insertion and deletion of unessential variables (the structure of these classes is described in the book by Jablonsky, Gavrilov and Kudriavtzev [5]. The obtained results are compared with the results developed by Moshkov in [6] that describe the worst case time complexity of decision trees.
One-Turn Regulated Pushdown Automata and Their Reduction
Authors: Meduna Alexander , Kolář Dušan
Published: December 2024

This paper discusses some simple and natural restrictions of regulated pushdown automata, whose moves are regulated by some control languages. Most importantly, it studies one-turn regulated pushdown automata and proves that they characterize the family of recursively enumerable languages. In fact, this characterization holds even for atomic one-turn regulated pushdown automata of a reduced size. This result is established in terms of acceptance by final state and empty pushdown, acceptance by final state, and acceptance by empty pushdown.
Construction of Pure Grammars
Authors: Novotný Miroslav
Published: December 2024

A construction is described assigning a pure grammar G_{mrn} to any language and to any integers 0≤m≤r≤n. This construction has the following property: If the sequence (G_{mrn})_{n≥r} has a limit G_{mr} for any r≥m and if the sequence (G_{mr})_{r≥m} has a limit, then the given language is generated by a pure grammar. By a limit of a sequence (a_{k})_{k≥k_{0}} we understand a member a_{k_{1}} of the sequence such that k_{1}≥k_{0} and a_{k}=a_{k_{1}} for any k≥k_{1}.
Risk-type Description of Control Variants
Authors: Terlikowski Tomasz
Published: December 2024

In this paper, we introduce the notion of risk-type description. The concept is strongly related to the definition of risk function, as analyzed in detail in [20]. The main difference consists in considering objects of other categories, different than those analyzed in [20]. The analysis shows relationships and differences between the two notions, both concerning the idea of risk in control.
On the Rlationship Between Monadic and Weak Monadic Second Order	Logic on Arbitrary Trees, with Applications to the mu-Calculus
Authors: Janin David , Lenzi Giacomo
Published: December 2024

In 1970 [26], in Weakly definable relations and special automata, Math. Log. and Found. of Set Theory, pp 1-23, Rabin shows that a language is recognizable by a tree automaton with Büchi like infinitary condition if and only if it is definable as the projection of a weakly definable language. In this paper, we refine this result characterizing such languages as those definable in the monadic Σ2 level of the quantifier alternation depth hierarchy of monadic second order logic (MSO). This new result also contributes to a better understanding of the relationship between the quantifier alternation depth of hierarchy of MSO and the fixpoint alternation depth hierarchy of the mu-calculus: it shows that the bisimulation invariant fragment of the monadic Σ2 level equals the νμ-level of the mu-calculus hierarchy.
Query Compilation under the disjunctive well-founded	semantics
Authors: Johnson Chris A.
Published: December 2024

A top-down method is presented for compiling queries in unstratified propositional disjunctive deductive databases under the disjunctive well-founded semantics. Compilation entails the construction of a set of compilation trees, and the run-time processing of the compiled query then amounts to checking that some such tree can be extended within the extensional database to yield a tree that encapsulates a proof of the original query. Issues surrounding the extension of our techniques to the first order level are discussed.
Knowledge Acquisition under Incomplete Knowledge using Methods from Formal	Concept Analysis: Part I
Authors: Holzer Richard
Published: December 2024

Formal contexts with unknown entries can be represented by three-valued contexts K=(G, M, {×, o, ?}, I), where a question mark indicates that it is not known whether the object g∈G has the attribute m∈M. To describe logical formulas between columns of such incomplete contexts the Kripke-semantics are used for propositional formulas over the set M of attributes. Attribute implications are considered as special propositional formulas. If a context is too large to be fully represented, an interactive computer algorithm may help the user to get maximal information (with respect to his knowledge) about the valid attribute implications of the unknown context. This computer algorithm is called "attribute exploration".
Algebraic Structures Related to Many Valued Logical Systems. Part	I: Heyting Wajsberg Algebras
Authors: Cattaneo Gianpiero , Ciucci Davide , Giuntini Roberto , Konig Martin
Published: December 2024

A bottom-up investigation of algebraic structures corresponding to many valued logical systems is made. Particular attention is given to the unit interval as a prototypical model of these kind of structures. At the top level of our construction, Heyting Wajsberg algebras are defined and studied. The peculiarity of this algebra is the presence of two implications as primitive operators. This characteristic is helpful in the study of abstract rough approximations.
Modeling and Verification of Reactive Systems using Rebeca
Authors: Sirjani Marjan , Movaghar Ali , Shali Amin , de Boer Frank S.
Published: December 2024

Actor-based modeling has been successfully applied to the representation of concurrent and distributed systems. Besides having an appropriate and efficient way for modeling these systems, one needs a formal verification approach for ensuring their correctness. In this paper, we develop an actor-based model for describing such systems, use temporal logic to specify properties of the model, and apply different abstraction and verification methods for verifying that the model meets its specification. We use a compositional verification approach for verifying safety properties of these models. For that we introduce a notion of component, based on an user-defined decomposition of the model. Components are more abstract than the model itself, and so we can reduce the state space of the model which makes it more amenable to model checking techniques. We prove that our abstraction technique preserves a set of behavioral specifications in temporal logic. The soundness of the abstraction is proved by the weak simulation relation between the constructs.
On Effective Methods for Diagnosis of Retaining Faults in	Circuits
Authors: Moshkova Albina
Published: December 2024

In the paper so-called retaining faults of combinatorial circuits are considered. It is proved that for iteration-free circuits there exist decision trees which solve the problem of circuit diagnosis relatively retaining faults and which depth is bounded from above by a linear function on the number of gates in circuits. For each closed class of Boolean functions a basis is found which is optimal from the point of view of complexity of diagnosis of formula-like circuits over this basis (during the procedure of diagnosis each formula-like circuit is transformed into an iteration-free circuit). Relationships are studied between two types of Shannon functions. A function of the first type characterizes the complexity of diagnosis of formula-like circuits realizing Boolean functions from a closed class. A function of the second type characterizes the complexity of formulas realizing Boolean functions from a closed class. The obtained relationships allowe to transfer some known results for Shannon functions of the second type on the case of Shannon functions of the first type.
Event Structures for Arbitrary Disruption
Authors: Fecher Harald , Majster-Cederbaum Mila
Published: December 2024

In process algebras that allow for some form of disruption, it is important to state when a process terminates. One option is to include a termination action √. Another approach is that the 'final' executed action of a process terminates the process. The semantics of the former approach has been investigated in the literature in detail, e.g. by providing consistent true-concurrency and operational descriptions. The 'final' executed action termination approach, which is more adequate for modelling, still lacks the existence of a detailed true concurrent description. In order to give a true concurrency model of such a termination view, we introduce a new class of event structures. This type of event structures models disabling by indicating sets of precursor events. We show that the introduced class of event structures has more expressive power with respect to event traces than the common event structures. We also give a classification of the expressive power in terms of sets of event traces. A consistency result of an operational and a denotational semantics is shown.
Towards a Framework for Modelling Systems with Rich Internal	Structures of States and Processes
Authors: Winkowski Józef
Published: December 2024

The paper is concerned with modelling distributed systems by specifying their states and processes. Processes are defined as activities in a universe of objects, each object with a set of possible internal states, each activity changing states of some objects and establishing or destroying relations among objects. Partial operations of composing processes sequenially and in parallel are defined. It is shown that certain sets of processes form together with these operations categories with additional structures and special properties, that processes of a system can be represented as morphisms of such categories, and that independence of processes can be characterized in a natural, purely algebraic way.
Very Simple Chaitin Machines for Concrete AIT
Authors: Stay Michael
Published: December 2024

In 1975, Chaitin introduced his celebrated Omega number, the halting probability of a universal Chaitin machine, a universal Turing machine with a prefix-free domain. The Omega number's bits are algorithmically random–there is no reason the bits should be the way they are, if we define "reason" to be a computable explanation smaller than the data itself. Since that time, only two explicit universal Chaitin machines have been proposed, both by Chaitin himself.

Concrete algorithmic information theory involves the study of particular universal Turing machines, about which one can state theorems with specific numerical bounds, rather than include terms like O(1). We present several new tiny Chaitin machines (those with a prefix-free domain) suitable for the study of concrete algorithmic information theory. One of the machines, which we call Keraia, is a binary encoding of lambda calculus based on a curried lambda operator. Source code is included in the appendices.

We also give an algorithm for restricting the domain of blank-endmarker machines to a prefix-free domain over an alphabet that does not include the endmarker; this allows one to take many universal Turing machines and construct universal Chaitin machines from them.
Information Divergence Criterion in Speech Signal	Recognition
Authors: Bocharov Igor , Lukin Pavel
Published: December 2024

The article discusses an application of Kullback-Leibler divergence to the recognition of speech signals and suggests three algorithms implementing this divergence criterion: correlation algorithm, spectral algorithm and filter algorithm. Discussion covers an original approach to the problem of speech variability and is illustrated with results of experimental speech signal modeling. The article gives a number of recommendations on the choice of appropriate model parameters and provides a comparison to some other methods of speech recognition.
A New Density-Based Scheme for Clustering Based on Genetic	Algorithm
Authors: Lin Chih-Yang , Chang Chin-Chen , Lin Chia-Chen
Published: December 2024

Density-based clustering can identify arbitrary data shapes and noises. Achieving good clustering performance necessitates regulating the appropriate parameters in the density-based clustering. To select suitable parameters successfully, this study proposes an interactive idea called GADAC to choose suitable parameters and accept the diverse radii for clustering. Adopting the diverse radii is the original idea employed to the density-based clustering, where the radii can be adjusted by the genetic algorithmto cover the clusters more accurately. Experimental results demonstrate that the noise and all clusters in any data shapes can be identified precisely in the proposed scheme. Additionally, the shape covering in the proposed scheme is more accurate than that in DBSCAN.
Similarity MV-algebras
Authors: Gerla B. , Leuştean I.
Published: December 2024

Similarities are an extension of equivalence relations to a fuzzy context. In this paper we introduce the class of similarity MV-algebras obtained as a generalization of the variety of MV-algebras by adding a binary operator playing the role of similarity. We further introduce the similarity Łukasiewicz logic and we prove a completeness theorem.
On the Axioms of Residuated Structures: Independence, Dependencies	and Rough Approximations
Authors: Ciucci Davide
Published: December 2024

Several residuated algebras are taken into account. The set of axioms defining each structure is reduced with the aim to obtain an independent axiomatization. Further, the relationship among all the algebras is studied and their dependencies outlined. Finally, rough approximation spaces are introduced in residuated lattices with involution and their algebraic structure outlined.
Pruning Operators for Disjunctive Logic Programming Systems
Authors: Calimeri Francesco , Faber Wolfgang , Pfeifer Gerald , Leone Nicola
Published: December 2024

Disjunctive Logic Programming (DLP) is an advanced formalism for knowledge representation and reasoning. The language of DLP is very expressive and supports the representation of problems of high computational complexity (specifically, all problems in the complexity class Σ ^p_2 =NP ^{NP} ). The DLP encoding of a large variety of problems is often very concise, simple, and elegant.

In this paper, we explain the computational process commonly performed by DLP systems, with a focus on search space pruning, which is crucial for the efficiency of such systems. We present two suitable operators for pruning (Fitting's and Well-founded), discuss their peculiarities and differences with respect to efficiency and effectiveness. We design an intelligent strategy for combining the two operators, exploiting the advantages of both. We implement our approach in DLV – the state-of-the-art DLP system – and perform some experiments. These experiments show interesting results, and evidence how the choice of the pruning operator affects the performance of DLP systems.
Logic Programming Representation of the Compound Term Composition	Algebra
Authors: Analyti Anastasia , Pachoulakis Ioannis
Published: December 2024

The Compound Term Composition Algebra (CTCA) is an algebra with four algebraic operators, which can be used to generate the valid (meaningful) compound terms of a given faceted taxonomy, in an efficient and flexible manner. The positive operations allow the derivation of valid compound terms through the declaration of a small set of valid compound terms. The negative operations allow the derivation of valid compound terms through the declaration of a small set of invalid compound terms. In this paper, we show how CTCA can be represented in logic programming with negation-as-failure, according to both Clark's and well-founded semantics. Indeed, the SLDNF-resolution can be used for checking compound term validity and well-formedness of an algebraic expression in polynomial time w.r.t. the size of the expression and the number of terms in the taxonomy. This result makes our logic programming representation a competitive alternative to imperative algorithms. Embedding of our logic programming representation to the programming environment of a web portal for a computer sales company is demonstrated.
Multiple Images Embedding Scheme Based on Moment Preserving Block	Truncation Coding
Authors: Hu Yu-Chen
Published: December 2024

A low-complexity grayscale image embedding scheme that can embed multiple secret images is proposed in this paper. In this scheme, different users can extract different secret images according to the secret keys they hold. To reduce the storage cost of the secret images, each of the secret images is first compressed using an improved version of the moment preserving block truncation coding scheme. The compressed message of each secret image is then encrypted by the DES cryptography system with different secret key and then embedded into the host image using the modulus least-significant-bit substitution technique.

According to the experimental results, it is shown that the proposed scheme consumes a little computational cost. Besides, different users can extract different number of secret images. In other words, the proposed scheme indeed provides a good approach for the hiding of grayscale images with access control.
Adaptive Merging of Prioritized Knowledge Bases
Authors: Liu Weiru , Qi Guilin , Bell David A.
Published: December 2024

In this paper, we propose an adaptive algorithm for merging n (⩾2) prioritized knowledge bases which takes into account the degrees of conflict and agreement among these knowledge bases. The algorithm first selects largely partially maximal consistent subsets (LPMCS) of sources by assessing how (partially) consistent the information in the subset is. Then within each of these created subsets, a maximal consistent subset is further selected and knowledge bases in it are merged with a suitable conjunctive operator based on the degree of agreement among them. This result is then merged with the remaining knowledge bases in the corresponding LPMCS in the second step through the relaxation of the minimum operator. Finally, the knowledge bases obtained from the second step are merged by a maximum operator. In comparison with other merging methods, our approach is more context dependent and is especially useful when most sources of information are in conflict.
Analysis of RTCP-nets with Reachability Graphs
Authors: Szpyrka Marcin
Published: December 2024

RTCP-nets are a subclass of timed coloured Petri nets defined for modelling and analysis of embedded real-time systems. One of the main advantages of strongly bounded RTCP-nets is a possibility to present the set of reachable states of an RTCP-net using a finite reachability and/or coverability graph. These graphs can be used to verify most of the net's properties, including the timing ones. The paper discusses analysis methods based on these graphs. A formal definition of RTCP-nets and a survey of their properties are also presented in the paper.
Tolerant Key Assignment for Enforcing Complicated Access Control	Policies in a Hierarchy
Authors: Chang Ya-Fen , Chang Chin-Chen
Published: December 2024

In 1998, Yeh et al. proposed a flexible key assignment scheme for enforcing complicated access control policies in a user matrix model. Later, Hwang indicated that Yeh et al.' scheme is susceptible to some security flaws. Thus, Lin et al. proposed a key assignment scheme for enforcing complicated access control policies in a hierarchy. However, there exist drawbacks in Lin et al.'s scheme: lack of efficiency and a large variation of the keys. Hence, we propose an efficient key assignment scheme in a hierarchy for enforcing the complicated access control policies. What is more, the secret key of one class is allowed to be changed several times without influencing the derivation key in our proposed scheme.
A Pricing Approach For Grid Resource Scheduling With QoS Guarantees
Authors: Chunlin Li , Layuan Li
Published: December 2024

The paper is targeted at concerning pricing approach for grid resource scheduling with QoS guarantees. The two major parties in Grid, namely, resource consumers who submit various applications, and resources providers who share their resources, usually have different motivations when they join the Grid. These incentives are presented by objective functions in scheduling. Economic grid QoS scheduling algorithm adopt both application-centric and resource-centric scheduling objective function aim to optimize the performance of each individual grid user and the performance of the grid resources. The economic cost and profit are considered by grid users and resource providers respectively. Objective functions and QoS scheduling optimization algorithms are proposed. QoS scheduling optimization is decomposed into two sub optimizations of grid user's cost and grid resource provider's profit by utilizing dynamic programming. QoS scheduling algorithm is an interactive process in economic market coordinating grid users and grid resource providers to achieve optimal QoS scheduling. Experiments are to compare the proposed economic QoS scheduling with three partial optimisation approaches, which only consider one criterion.
Advances in Symmetric Sandpiles
Authors: Formenti Enrico , Masson Benoît , Pisokas Theophilos
Published: December 2024

A symmetric version of the well-known SPM model for sandpiles is introduced. We prove that the new model has fixed-point dynamics. Although there might be several fixed points, a precise description of the fixed points is given. Moreover, we provide a simple closed formula for counting the number of fixed points originated by initial conditions made of a single column of grains. Bounds for the transient length are also given.
Particle Swarms for Linearly Constrained Optimisation
Authors: Paquet Ulrich , Engelbrecht Andries P.
Published: December 2024

Particle Swarm Optimisation (PSO) has proved to be a very useful algorithm to optimise unconstrained functions. This paper extends PSO to a Linear PSO (LPSO) to optimise functions constrained by a set of equality constraints of the form Ax=b. By initialising particles within a constrained hyperplane, the LPSO is guaranteed to 'fly' only through this hyperplane. A criterion on the initial swarm stipulates when the optimum solution can possibly be reached. The Linear PSO is modified to the Converging Linear PSO, for which it is proved to always find at least a local minimum. Experimental results are given, which compare the LPSO and CLPSO with Genocop II.
An Image Retrieval Method Based on Color-Complexity and	Spatial-Histogram Features
Authors: Wu Hsien-Chu , Chang Chin-Chen
Published: December 2024

This paper proposes two kinds of image features. One feature is the spatial-histogram feature. It combines the color histogram feature and the information about the dimensional position of pixels in an image to record the distribution of the pixels' colors that are present in different spatial positions within an image. The other image feature proposed in this paper is the color-complexity feature, which can be used to describe the change of pixel colors in the image. From the experimental results, ANMRR value is provided and we observe that the image retrieval system based on these two kinds of image features can provide a fairly good accuracy rate in image retrieval. Moreover, it has the capacity to tolerate errors; that is, for images that are damaged by rotation, shift, or color variant attacks, their similar image pairs can still be retrieved from the image database. Thus, the accuracy and flexibility of the image retrieval system are drastically improved.
Efficient Algorithm of Affine Form Searching forWeakly Specified	Boolean Function
Authors: Porwik Piotr
Published: December 2024

This paper presents the spectralmethod of recognition of an incompletely defined Boolean function. The main goal of analysis is fast estimation whether a given single output function can be extended to affine form. Furthermore, a simple extension algorithm is proposed for functions, for which the affine form is reachable. The algorithm is compared with other methods. Theoretical and experimental results demonstrate the efficiency of the presented approach.
An Algebraic Foundation for Linguistic Reasoning
Authors: Huynh Van Nam , Nakamori Yoshiteru , Murai Tetsuya
Published: December 2024

It is well known that algebraization has been successfully applied to classical and nonclassical logics (Rasiowa and Sikorski, 1968). Following this direction, an ordered-based approach to the problem of finding out a tool to describe algebraic semantics of Zadeh's fuzzy logic has been introduced and developed by Nguyen Cat-Ho and colleagues during the last decades. In this line of research, RH algebra has been introduced in [20] as a unified algebraic approach to the natural structure of linguistic domains of linguistic variables. It was shown that every RH algebra of a linguistic variable with a chain of the primary terms is a distributive lattice. In this paper we will examine algebraic structures of RH algebras corresponding to linguistic domains having exactly two distinct primary terms, one being an antonym of the other, called symmetrical RH algebras. Computational results for the relatively pseudo-complement operation in these algebras will be given.
A Logic-Based Approach to Finding Explanations for Discrepancies	in Optimistic Plan Execution
Authors: Eiter Thomas , Erdem Esra , Faber Wolfgang , Senko Ján
Published: December 2024

Consider an agent executing a plan with nondeterministic actions, in a dynamic environment, which might fail. Suppose that she is given a description of this action domain, including specifications of effects of actions, and a set of trajectories for the execution of this plan, where each trajectory specifies a possible execution of the plan in this domain. After executing some part of the plan, suppose that she obtains information about the current state of the world, and notices that she is not at a correct state relative to the given trajectories. How can she find an explanation (a point of failure) for such a discrepancy? An answer to this question can be useful for different purposes. In the context of execution monitoring, points of failure can determine some checkpoints that specify when to check for discrepancies, and they can sometimes be used for recovering from discrepancies that cause plan failures. At the modeling level, points of failure may provide useful insight into the action domain for a better understanding of the domain, or reveal errors in the formalization of the domain. We study the question above in a general logic-based knowledge representation framework, which can accommodate nondeterminism and concurrency. In this framework, we define a discrepancy and an explanation for it, and analyze the computational complexity of detecting discrepancies and finding explanations for them. We introduce a method for computing explanations, and report about a realization of this method using DLV ^K , which is a logic-programming based system for reasoning about actions and change.
A Propositional Proof System with Quantification Over	Permutations
Authors: Herman Grzegorz , Paterson Tim , Soltys Michael
Published: December 2024

We introduce a new propositional proof system, which we call H, that allows quantification over permutations. In H we may write (∃ab)α and (∀ab)α, which is semantically equivalent to α(a,b)∨α(b,a) and α(a,b)∧ α(b,a), respectively. We show that H with cuts restricted to Σ _1 formulas (we denote this system H _1 ) simulates efficiently the Hajós calculus (HC) for constructing graphs which are non-3-colorable. This shows that short proofs over formulas that assert the existence of permutations can capture polynomial time reasoning (as by [9], HC is equivalent in strength to EF, which in turn captures polytime reasoning). We also show that EF simulates efficiently H ^*_1 , which is H _1 with proofs restricted to being tree-like. In short, we show that H ^*_1 ⩽ _p EF⩽ _p H _1 .
Predicate Introduction for Logics with Fixpoint Semantics. Part	II: Autoepistemic Logic
Authors: Vennekens Joost , Wittocx Johan , Mariën Maarten , Denecker Marc
Published: December 2024

We study the transformation of "predicate introduction" in non-monotonic logics. By this, we mean the act of replacing a complex formula by a newly defined predicate. From a knowledge representation perspective, such transformations can be used to eliminate redundancy or to simplify a theory. From a more practical point of view, they can also be used to transform a theory into a normal form imposed by certain inference programs or theorems. In a companion paper, we developed an algebraic theory that considers predicate introduction within the framework of "approximation theory", a fixpoint theory for non-monotone operators that generalizes all main semantics of various non-monotonic logics, including logic programming, default logic and autoepistemic logic. We then used these results to show that certain logic programming transformations are equivalence preserving under, among others, both the stable and well-founded semantics. In this paper, we now apply the same algebraic results to autoepistemic logic and prove that a transformation to reduce the nesting depth of modal operators is equivalence preserving under a family of semantics for this logic. This not only provides useful theorems for autoepistemic logic, but also demonstrates that our algebraic theory does indeed capture the essence of predicate introduction in a generally applicable way.
A Comparative Analysis of Possibilistic Variances and Covariances	of Fuzzy Numbers
Authors: Zhang Wei-Guo , Wang Ying-Luo
Published: December 2024

In this paper, we introduce a new crisp possibilistic variance and a new crisp possibilistic covariance of fuzzy numbers, which are different from those introduced by Carlsson and Fullér. We show that the possibilistic variance and covariance preserve many properties of variance and covariance in probability theory. Furthermore, we investigate the relationship between several crisp possibilistic variances and covariances of fuzzy numbers.
RFCM: A Hybrid Clustering Algorithm Using Rough and Fuzzy Sets
Authors: Maji Pradipta , Pal Sankar K.
Published: December 2024

A hybrid unsupervised learning algorithm, termed as rough-fuzzy c-means, is proposed in this paper. It comprises a judicious integration of the principles of rough sets and fuzzy sets. While the concept of lower and upper approximations of rough sets deals with uncertainty, vagueness, and incompleteness in class definition, the membership function of fuzzy sets enables efficient handling of overlapping partitions. The concept of crisp lower bound and fuzzy boundary of a class, introduced in rough-fuzzy c-means, enables efficient selection of cluster prototypes. Several quantitative indices are introduced based on rough sets for evaluating the performance of the proposed c-means algorithm. The effectiveness of the algorithm, along with a comparison with other algorithms, has been demonstrated on a set of real life data sets.
Outfix-Free Regular Languages and Prime Outfix-Free	Decomposition
Authors: Han Yo-Sub , Wood Derick
Published: December 2024

A string x is an outfix of a string y if there is a string w such that x _1 wx _2 = y and x = x _1 x _2 . A set X of strings is outfix-free if no string in X is an outfix of any other string in X. Based on the properties of outfix strings, we develop a polynomial-time algorithm that determines outfix-freeness of regular languages. Note that outfix-free regular languages are always finite. We consider two cases: 1) a language is given as a finite set of strings and 2) a language is given by a finite-state automaton. Furthermore, we investigate the prime outfix-free decomposition of outfixfree regular languages and design a linear-time algorithm that computes prime outfix-free decomposition for outfix-free regular languages. We also demonstrate the uniqueness of prime outfix-free decomposition.
Invariance Under Stuttering in a Temporal Logic without the "Until" Operator
Authors: Kaminski Michael
Published: December 2024

We show that a stutter-invariant property is expressible in propositional temporal logic without the "until" operator if and only if it is expressible in the Generalized Temporal Logic of Actions.
Abduction for Accessing Information Sources
Authors: Meghini Carlo , Tzitzikas Yannis , Spyratos Nicolas
Published: December 2024

We consider a general form of information sources, consisting of a set of objects classified by terms arranged in a taxonomy. The query-based access to the information stored in sources of this kind, is plagued with uncertainty, due, among other things, to the possible linguisticmismatch between the user and the object classification. To overcome this uncertainty in all situations in which the user is not finding the desired information and is not willing or able to state a new query, the study proposes to extend the classification, in a way that is as reasonable as possible with respect to the original one. By equating reasonableness with logical implication, the sought extension turns out to be an explanation of the classification, captured by abduction. The problem of query evaluation on information sources extended in this way is studied and a polynomial time algorithm is provided for the general case, in which no hypothesis is made on the structure of the taxonomy. The algorithm is successively specialized on a most common kind of information sources, namely sources whose taxonomy can be represented as a directed acyclic graph. It is shown that query evaluation on extended sources is easier for this kind of sources. Finally, two applications of the method are presented, which capture very important aspects of information access: information browsing and query result ranking.
Multi-Valued MSO Logics OverWords and Trees
Authors: Droste Manfred , Kuich Werner , Rahonis George
Published: December 2024

We introduce multi-valued Büchi and Muller automata over distributive lattices and a multi-valued MSO logic for infinite words. For this logic, we prove the expressive equivalence of ω-recognizable and MSO-definable infinitary formal power series over distributive lattices with negation function. Then we consider multi-valued Muller tree automata and a multi-valued MSO logic for trees over distributive lattices. For this logic, we establish a version of Rabin's theorem for infinitary tree series.
Time Distribution in Structural Workflow Nets
Authors: Chrz�stowski-Wachtel Piotr , Findeisen Paweł , Wolny Grzegorz
Published: December 2024

Workflows with transition execution times having exponential distributions are considered. The aim is to determine the overall execution time without looking into the reachability space and its analysis using Markov processes. We concentrate on the so called structural workflows, which are represented with Petri nets constructed by means of specific refinement rules. With each refinement rule (sequence, choice, parallelization, loop) we associate formulas which allow to compute the overall execution time distribution.

The class of exponential distributions is too narrow to keep the result within itself. We analyze the so called exponential polynomials, generalizing exponential distributions. They are closed under SUM and MAX functions. This closure property combined with the knowledge of refinements history enables us to find the requested formulas.
Approximation Space and LEM2-like Algorithms for Computing Local	Coverings
Authors: Grzymala-Busse Jerzy W. , Rz�sa Wojciech
Published: December 2024

In this paper we discuss approximation spaces that are useful for studying local lower and upper approximations. Set definability and properties of the approximation space, including best approximations, are considered as well. Finding best approximations is a NP-hard problem. Finally, we present LEM2-like algorithms for determining local lower and upper coverings for a given incomplete data set. Lower and upper approximations, associated with these coverings, are sub-optimal.
VerICS 2007 - a Model Checker for Knowledge and Real-Time
Authors: Kacprzak Magdalena , Nabiałek Wojciech , Niewiadomski Artur , Penczek Wojciech , Półrola Agata , Szreter Maciej , Woźna Bożena , Zbrzezny Andrzej
Published: December 2024

The papers presents the current stage of the development of VerICS - a model checker for real-time and multi-agent systems. Depending on the type of a system considered, it enables to test various classes of properties - from reachability to temporal, epistemic and deontic formulas. The model checking methods used to this aim include both SAT-based and enumerative ones. In the paper we focus on new features of the verifier: SAT-based model checking for multi-agent systems and several extensions and improvements to real-time systems' verification.
Modelling and Simulation of Quantum Teleportation and Dense Coding	Using Predicate/Transition-Nets
Authors: Varpaaniemi Kimmo , Ojala Leo
Published: December 2024

Reachability analysis is one of the most successful methods used in design and validation of protocols for classical communication, whereas the predicate/transition-net formalism is one of the most appropriate formalisms for reachability analysis oriented modelling.

Quantum teleportation and dense coding are non-classical communication protocols that have been widely researched in the field of quantum computing. In this article, we present predicate/transitionnet models of these two protocols and use the PROD reachability analysis tool for analysing the models.
On Rational Stochastic Languages
Authors: Denis François , Esposito Yann
Published: December 2024

The goal of the present paper is to provide a study of rational stochastic languages over a semiring K ∈ {Q,R,Q ^+ ,R ^+ }. A rational stochastic language is a probability distribution over a free monoid Σ*, which is rational over K, that is, which can be generated by a multiplicity automaton with parameters in K. We study the relations between the classes of rational stochastic languages S ^{rat} _K (Σ). We define the notion of residual language of a stochastic language and we use it to investigate properties of several subclasses of rational stochastic languages. Then, we study the representation of rational stochastic languages by means of multiplicity automata. Lastly, we show some connections between properties of rational stochastic languages and results obtained in the field of probabilistic grammatical inference.