OpenRaiser/Intern-Atlas huggingface dataset:
On Winning Conditions of High Borel Complexity in Pushdown Games
Venue: arXiv cs.LO 2008
Year: 2008

Some decidable winning conditions of arbitrarily high finite Borel complexity for games on finite graphs or on pushdown graphs have been recently presented by O. Serre in [ Games with Winning Conditions of High Borel Complexity, in the Proceedings of the International Conference ICALP 2004, LNCS, Volume 3142, p. 1150-1162 ]. We answer in this paper several questions which were raised by Serre in the above cited paper. We first show that, for every positive integer n, the class C_n(A), which arises in the definition of decidable winning conditions, is included in the class of non-ambiguous context free omega languages, and that it is neither closed under union nor under intersection. We prove also that there exists pushdown games, equipped with such decidable winning conditions, 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.
Closure Properties of Locally Finite Omega Languages
Venue: arXiv cs.LO 2008
Year: 2008

Locally finite omega languages were introduced by Ressayre in [Journal of Symbolic Logic, Volume 53, No. 4, p.1009-1026]. They generalize omega languages accepted by finite automata or defined by monadic second order sentences. We study here closure properties of the family LOC_omega of locally finite omega languages. In particular we show that the class LOC_omega is neither closed under intersection nor under complementation, giving an answer to a question of Ressayre.
On the Throughput Allocation for Proportional Fairness in Multirate IEEE 802.11 DCF under General Load Conditions
Venue: arXiv cs.NI 2008
Year: 2008

This paper presents a modified proportional fairness (PF) criterion suitable for mitigating the \textit{rate anomaly} problem of multirate IEEE 802.11 Wireless LANs employing the mandatory Distributed Coordination Function (DCF) option. Compared to the widely adopted assumption of saturated network, the proposed criterion can be applied to general networks whereby the contending stations are characterized by specific packet arrival rates, $λ_s$, and transmission rates $R_d^{s}$. The throughput allocation resulting from the proposed algorithm is able to greatly increase the aggregate throughput of the DCF while ensuring fairness levels among the stations of the same order of the ones available with the classical PF criterion. Put simply, each station is allocated a throughput that depends on a suitable normalization of its packet rate, which, to some extent, measures the frequency by which the station tries to gain access to the channel. Simulation results are presented for some sample scenarios, confirming the effectiveness of the proposed criterion.
The Application of Bayesian Optimization and Classifier Systems in Nurse Scheduling
Venue: arXiv cs.NE 2008
Year: 2008

Two ideas taken from Bayesian optimization and classifier systems are presented for personnel scheduling based on choosing a suitable scheduling rule from a set for each persons assignment. Unlike our previous work of using genetic algorithms whose learning is implicit, the learning in both approaches is explicit, i.e. we are able to identify building blocks directly. To achieve this target, the Bayesian optimization algorithm builds a Bayesian network of the joint probability distribution of the rules used to construct solutions, while the adapted classifier system assigns each rule a strength value that is constantly updated according to its usefulness in the current situation. Computational results from 52 real data instances of nurse scheduling demonstrate the success of both approaches. It is also suggested that the learning mechanism in the proposed approaches might be suitable for other scheduling problems.
Groups from Cyclic Infrastructures and Pohlig-Hellman in Certain Infrastructures
Venue: arXiv cs.CR 2008
Year: 2008

In discrete logarithm based cryptography, a method by Pohlig and Hellman allows solving the discrete logarithm problem efficiently if the group order is known and has no large prime factors. The consequence is that such groups are avoided. In the past, there have been proposals for cryptography based on cyclic infrastructures. We will show that the Pohlig-Hellman method can be adapted to certain cyclic infrastructures, which similarly implies that certain infrastructures should not be used for cryptography. This generalizes a result by Müller, Vanstone and Zuccherato for infrastructures obtained from hyperelliptic function fields. We recall the Pohlig-Hellman method, define the concept of a cyclic infrastructure and briefly describe how to obtain such infrastructures from certain function fields of unit rank one. Then, we describe how to obtain cyclic groups from discrete cyclic infrastructures and how to apply the Pohlig-Hellman method to compute absolute distances, which is in general a computationally hard problem for cyclic infrastructures. Moreover, we give an algorithm which allows to test whether an infrastructure satisfies certain requirements needed for applying the Pohlig-Hellman method, and discuss whether the Pohlig-Hellman method is applicable in infrastructures obtained from number fields. Finally, we discuss how this influences cryptography based on cyclic infrastructures.
Upper Bound on Error Exponent of Regular LDPC Codes Transmitted over the BEC
Venue: arXiv cs.IT 2008
Year: 2008

The error performance of the ensemble of typical LDPC codes transmitted over the binary erasure channel (BEC) is analyzed. In the past, lower bounds on the error exponents were derived. In this paper a probabilistic upper bound on this error exponent is derived. This bound holds with some confidence level.
Logical Queries over Views: Decidability and Expressiveness
Venue: arXiv cs.LO 2008
Year: 2008

We study the problem of deciding satisfiability of first order logic queries over views, our aim being to delimit the boundary between the decidable and the undecidable fragments of this language. Views currently occupy a central place in database research, due to their role in applications such as information integration and data warehousing. Our main result is the identification of a decidable class of first order queries over unary conjunctive views that generalises the decidability of the classical class of first order sentences over unary relations, known as the Lowenheim class. We then demonstrate how various extensions of this class lead to undecidability and also provide some expressivity results. Besides its theoretical interest, our new decidable class is potentially interesting for use in applications such as deciding implication of complex dependencies, analysis of a restricted class of active database rules, and ontology reasoning.
KohonAnts: A Self-Organizing Ant Algorithm for Clustering and Pattern Classification
Venue: arXiv cs.NE 2008
Year: 2008

In this paper we introduce a new ant-based method that takes advantage of the cooperative self-organization of Ant Colony Systems to create a naturally inspired clustering and pattern recognition method. The approach considers each data item as an ant, which moves inside a grid changing the cells it goes through, in a fashion similar to Kohonen's Self-Organizing Maps. The resulting algorithm is conceptually more simple, takes less free parameters than other ant-based clustering algorithms, and, after some parameter tuning, yields very good results on some benchmark problems.
Building Better Nurse Scheduling Algorithms
Venue: arXiv cs.NE 2008
Year: 2008

The aim of this research is twofold: Firstly, to model and solve a complex nurse scheduling problem with an integer programming formulation and evolutionary algorithms. Secondly, to detail a novel statistical method of comparing and hence building better scheduling algorithms by identifying successful algorithm modifications. The comparison method captures the results of algorithms in a single figure that can then be compared using traditional statistical techniques. Thus, the proposed method of comparing algorithms is an objective procedure designed to assist in the process of improving an algorithm. This is achieved even when some results are non-numeric or missing due to infeasibility. The final algorithm outperforms all previous evolutionary algorithms, which relied on human expertise for modification.
Towards a Symbolic-Numeric Method to Compute Puiseux Series: The Modular Part
Venue: arXiv cs.SC 2008
Year: 2008

We have designed a new symbolic-numeric strategy to compute efficiently and accurately floating point Puiseux series defined by a bivariate polynomial over an algebraic number field. In essence, computations modulo a well chosen prime $p$ are used to obtain the exact information required to guide floating point computations. In this paper, we detail the symbolic part of our algorithm: First of all, we study modular reduction of Puiseux series and give a good reduction criterion to ensure that the information required by the numerical part is preserved. To establish our results, we introduce a simple modification of classical Newton polygons, that we call "generic Newton polygons", which happen to be very convenient. Then, we estimate the arithmetic complexity of computing Puiseux series over finite fields and improve known bounds. Finally, we give bit-complexity bounds for deterministic and randomized versions of the symbolic part. The details of the numerical part will be described in a forthcoming paper.
On the Diversity-Multiplexing Tradeoff in Multiple-Relay Network
Venue: arXiv cs.IT 2008
Year: 2008

This paper studies the setup of a multiple-relay network in which $K$ half-duplex multiple-antenna relays assist in the transmission between a/several multiple-antenna transmitter(s) and a multiple-antenna receiver. Each two nodes are assumed to be either connected through a quasi-static Rayleigh fading channel, or disconnected. We propose a new scheme, which we call \textit{random sequential} (RS), based on the amplify-and-forward relaying. We prove that for general multiple-antenna multiple-relay networks, the proposed scheme achieves the maximum diversity gain. Furthermore, we derive diversity-multiplexing tradeoff (DMT) of the proposed RS scheme for general single-antenna multiple-relay networks. It is shown that for single-antenna two-hop multiple-access multiple-relay ($K>1$) networks (without direct link between the transmitter(s) and the receiver), the proposed RS scheme achieves the optimum DMT. However, for the case of multiple access single relay setup, we show that the RS scheme reduces to the naive amplify-and-forward relaying and is not optimum in terms of DMT, while the dynamic decode-and-forward scheme is shown to be optimum for this scenario.
Eye-Tracking Evolutionary Algorithm to minimize user's fatigue in IEC applied to Interactive One-Max problem
Venue: arXiv cs.AI 2008
Year: 2008

In this paper, we describe a new algorithm that consists in combining an eye-tracker for minimizing the fatigue of a user during the evaluation process of Interactive Evolutionary Computation. The approach is then applied to the Interactive One-Max optimization problem.
Succinct Data Structures for Retrieval and Approximate Membership
Venue: arXiv cs.DS 2008
Year: 2008

The retrieval problem is the problem of associating data with keys in a set. Formally, the data structure must store a function f: U ->{0,1}^r that has specified values on the elements of a given set S, a subset of U, |S|=n, but may have any value on elements outside S. Minimal perfect hashing makes it possible to avoid storing the set S, but this induces a space overhead of Theta(n) bits in addition to the nr bits needed for function values. In this paper we show how to eliminate this overhead. Moreover, we show that for any k query time O(k) can be achieved using space that is within a factor 1+e^{-k} of optimal, asymptotically for large n. If we allow logarithmic evaluation time, the additive overhead can be reduced to O(log log n) bits whp. The time to construct the data structure is O(n), expected. A main technical ingredient is to utilize existing tight bounds on the probability of almost square random matrices with rows of low weight to have full row rank. In addition to direct constructions, we point out a close connection between retrieval structures and hash tables where keys are stored in an array and some kind of probing scheme is used. Further, we propose a general reduction that transfers the results on retrieval into analogous results on approximate membership, a problem traditionally addressed using Bloom filters. Again, we show how to eliminate the space overhead present in previously known methods, and get arbitrarily close to the lower bound. The evaluation procedures of our data structures are extremely simple (similar to a Bloom filter). For the results stated above we assume free access to fully random hash functions. However, we show how to justify this assumption using extra space o(n) to simulate full randomness on a RAM.
Asymptotically Optimum Universal One-Bit Watermarking for Gaussian Covertexts and Gaussian Attacks
Venue: arXiv cs.IT 2008
Year: 2008

The problem of optimum watermark embedding and detection was addressed in a recent paper by Merhav and Sabbag, where the optimality criterion was the maximum false-negative error exponent subject to a guaranteed false-positive error exponent. In particular, Merhav and Sabbag derived universal asymptotically optimum embedding and detection rules under the assumption that the detector relies solely on second order joint empirical statistics of the received signal and the watermark. In the case of a Gaussian host signal and a Gaussian attack, however, closed-form expressions for the optimum embedding strategy and the false-negative error exponent were not obtained in that work. In this paper, we derive such expressions, again, under the universality assumption that neither the host variance nor the attack power are known to either the embedder or the detector. The optimum embedding rule turns out to be very simple and with an intuitively-appealing geometrical interpretation. The improvement with respect to existing sub-optimum schemes is demonstrated by displaying the optimum false-negative error exponent as a function of the guaranteed false-positive error exponent.
Grammar-Based Random Walkers in Semantic Networks
Venue: arXiv cs.AI 2008
Year: 2008

Semantic networks qualify the meaning of an edge relating any two vertices. Determining which vertices are most "central" in a semantic network is difficult because one relationship type may be deemed subjectively more important than another. For this reason, research into semantic network metrics has focused primarily on context-based rankings (i.e. user prescribed contexts). Moreover, many of the current semantic network metrics rank semantic associations (i.e. directed paths between two vertices) and not the vertices themselves. This article presents a framework for calculating semantically meaningful primary eigenvector-based metrics such as eigenvector centrality and PageRank in semantic networks using a modified version of the random walker model of Markov chain analysis. Random walkers, in the context of this article, are constrained by a grammar, where the grammar is a user defined data structure that determines the meaning of the final vertex ranking. The ideas in this article are presented within the context of the Resource Description Framework (RDF) of the Semantic Web initiative.
SecMon: End-to-End Quality and Security Monitoring System
Venue: arXiv cs.MM 2008
Year: 2008

The Voice over Internet Protocol (VoIP) is becoming a more available and popular way of communicating for Internet users. This also applies to Peer-to-Peer (P2P) systems and merging these two have already proven to be successful (e.g. Skype). Even the existing standards of VoIP provide an assurance of security and Quality of Service (QoS), however, these features are usually optional and supported by limited number of implementations. As a result, the lack of mandatory and widely applicable QoS and security guaranties makes the contemporary VoIP systems vulnerable to attacks and network disturbances. In this paper we are facing these issues and propose the SecMon system, which simultaneously provides a lightweight security mechanism and improves quality parameters of the call. SecMon is intended specially for VoIP service over P2P networks and its main advantage is that it provides authentication, data integrity services, adaptive QoS and (D)DoS attack detection. Moreover, the SecMon approach represents a low-bandwidth consumption solution that is transparent to the users and possesses a self-organizing capability. The above-mentioned features are accomplished mainly by utilizing two information hiding techniques: digital audio watermarking and network steganography. These techniques are used to create covert channels that serve as transport channels for lightweight QoS measurement's results. Furthermore, these metrics are aggregated in a reputation system that enables best route path selection in the P2P network. The reputation system helps also to mitigate (D)DoS attacks, maximize performance and increase transmission efficiency in the network.
Effects of High-Order Co-occurrences on Word Semantic Similarities
Venue: arXiv cs.CL 2008
Year: 2008

A computational model of the construction of word meaning through exposure to texts is built in order to simulate the effects of co-occurrence values on word semantic similarities, paragraph by paragraph. Semantic similarity is here viewed as association. It turns out that the similarity between two words W1 and W2 strongly increases with a co-occurrence, decreases with the occurrence of W1 without W2 or W2 without W1, and slightly increases with high-order co-occurrences. Therefore, operationalizing similarity as a frequency of co-occurrence probably introduces a bias: first, there are cases in which there is similarity without co-occurrence and, second, the frequency of co-occurrence overestimates similarity.
Graphical Estimation of Permeability Using RST&NFIS
Venue: arXiv cs.NE 2008
Year: 2008

This paper pursues some applications of Rough Set Theory (RST) and neural-fuzzy model to analysis of "lugeon data". In the manner, using Self Organizing Map (SOM) as a pre-processing the data are scaled and then the dominant rules by RST, are elicited. Based on these rules variations of permeability in the different levels of Shivashan dam, Iran has been highlighted. Then, via using a combining of SOM and an adaptive Neuro-Fuzzy Inference System (NFIS) another analysis on the data was carried out. Finally, a brief comparison between the obtained results of RST and SOM-NFIS (briefly SONFIS) has been rendered.
Distributed Consensus over Wireless Sensor Networks Affected by Multipath Fading
Venue: arXiv cs.DC 2008
Year: 2008

The design of sensor networks capable of reaching a consensus on a globally optimal decision test, without the need for a fusion center, is a problem that has received considerable attention in the last years. Many consensus algorithms have been proposed, with convergence conditions depending on the graph describing the interaction among the nodes. In most works, the graph is undirected and there are no propagation delays. Only recently, the analysis has been extended to consensus algorithms incorporating propagation delays. In this work, we propose a consensus algorithm able to converge to a globally optimal decision statistic, using a wideband wireless network, governed by a fairly simple MAC mechanism, where each link is a multipath, frequency-selective, channel. The main contribution of the paper is to derive necessary and sufficient conditions on the network topology and sufficient conditions on the channel transfer functions guaranteeing the exponential convergence of the consensus algorithm to a globally optimal decision value, for any bounded delay condition.
RubberEdge: Reducing Clutching by Combining Position and Rate Control with Elastic Feedback
Venue: arXiv cs.HC 2008
Year: 2008

Position control devices enable precise selection, but significant clutching degrades performance. Clutching can be reduced with high control-display gain or pointer acceleration, but there are human and device limits. Elastic rate control eliminates clutching completely, but can make precise selection difficult. We show that hybrid position-rate control can outperform position control by 20% when there is significant clutching, even when using pointer acceleration. Unlike previous work, our RubberEdge technique eliminates trajectory and velocity discontinuities. We derive predictive models for position control with clutching and hybrid control, and present a prototype RubberEdge position-rate control device including initial user feedback.
Agent-Based Perception of an Environment in an Emergency Situation
Venue: arXiv cs.AI 2008
Year: 2008

We are interested in the problem of multiagent systems development for risk detecting and emergency response in an uncertain and partially perceived environment. The evaluation of the current situation passes by three stages inside the multiagent system. In a first time, the situation is represented in a dynamic way. The second step, consists to characterise the situation and finally, it is compared with other similar known situations. In this paper, we present an information modelling of an observed environment, that we have applied on the RoboCupRescue Simulation System. Information coming from the environment are formatted according to a taxonomy and using semantic features. The latter are defined thanks to a fine ontology of the domain and are managed by factual agents that aim to represent dynamically the current situation.
Explicit Learning: an Effort towards Human Scheduling Algorithms
Venue: arXiv cs.NE 2008
Year: 2008

Scheduling problems are generally NP-hard combinatorial problems, and a lot of research has been done to solve these problems heuristically. However, most of the previous approaches are problem-specific and research into the development of a general scheduling algorithm is still in its infancy. Mimicking the natural evolutionary process of the survival of the fittest, Genetic Algorithms (GAs) have attracted much attention in solving difficult scheduling problems in recent years. Some obstacles exist when using GAs: there is no canonical mechanism to deal with constraints, which are commonly met in most real-world scheduling problems, and small changes to a solution are difficult. To overcome both difficulties, indirect approaches have been presented (in [1] and [2]) for nurse scheduling and driver scheduling, where GAs are used by mapping the solution space, and separate decoding routines then build solutions to the original problem.
A Semi-Automatic Framework to Discover Epistemic Modalities in Scientific Articles
Venue: arXiv cs.CL 2008
Year: 2008

Documents in scientific newspapers are often marked by attitudes and opinions of the author and/or other persons, who contribute with objective and subjective statements and arguments as well. In this respect, the attitude is often accomplished by a linguistic modality. As in languages like english, french and german, the modality is expressed by special verbs like can, must, may, etc. and the subjunctive mood, an occurrence of modalities often induces that these verbs take over the role of modality. This is not correct as it is proven that modality is the instrument of the whole sentence where both the adverbs, modal particles, punctuation marks, and the intonation of a sentence contribute. Often, a combination of all these instruments are necessary to express a modality. In this work, we concern with the finding of modal verbs in scientific texts as a pre-step towards the discovery of the attitude of an author. Whereas the input will be an arbitrary text, the output consists of zones representing modalities.