OpenRaiser/Intern-Atlas huggingface dataset:
Natural Halting Probabilities, Partial Randomness, and Zeta Functions
Venue: arXiv cs.CC 2006
Year: 2006

We introduce the zeta number, natural halting probability and natural complexity of a Turing machine and we relate them to Chaitin's Omega number, halting probability, and program-size complexity. A classification of Turing machines according to their zeta numbers is proposed: divergent, convergent and tuatara. We prove the existence of universal convergent and tuatara machines. Various results on (algorithmic) randomness and partial randomness are proved. For example, we show that the zeta number of a universal tuatara machine is c.e. and random. A new type of partial randomness, asymptotic randomness, is introduced. Finally we show that in contrast to classical (algorithmic) randomness--which cannot be naturally characterised in terms of plain complexity--asymptotic randomness admits such a characterisation.
Characterization of Pentagons Determined by Two X-rays
Venue: arXiv cs.CG 2006
Year: 2006

This paper contains some results of pentagons which can be determined by two X-rays. The results reveal this problem is more complicated.
A New Quartet Tree Heuristic for Hierarchical Clustering
Venue: arXiv cs.DS 2006
Year: 2006

We consider the problem of constructing an an optimal-weight tree from the 3*(n choose 4) weighted quartet topologies on n objects, where optimality means that the summed weight of the embedded quartet topologiesis optimal (so it can be the case that the optimal tree embeds all quartets as non-optimal topologies). We present a heuristic for reconstructing the optimal-weight tree, and a canonical manner to derive the quartet-topology weights from a given distance matrix. The method repeatedly transforms a bifurcating tree, with all objects involved as leaves, achieving a monotonic approximation to the exact single globally optimal tree. This contrasts to other heuristic search methods from biological phylogeny, like DNAML or quartet puzzling, which, repeatedly, incrementally construct a solution from a random order of objects, and subsequently add agreement values.
Lower bounds and complete problems in nondeterministic linear time and sublinear space complexity classes
Venue: arXiv cs.CC 2006
Year: 2006

Proving lower bounds remains the most difficult of tasks in computational complexity theory. In this paper, we show that whereas most natural NP-complete problems belong to NLIN (linear time on nondeterministic RAMs), some of them, typically the planar versions of many NP-complete problems are recognized by nondeterministic RAMs in linear time and sublinear space. The main results of this paper are the following: as the second author did for NLIN, we give exact logical characterizations of nondeterministic polynomial time-space complexity classes; we derive from them a class of problems, which are complete in these classes, and as a consequence of such a precise result and of some recent separation theorems using diagonalization, prove time-space lower bounds for these problems.
The Completeness of Propositional Resolution: A Simple and Constructive<br> Proof
Venue: arXiv cs.LO 2006
Year: 2006

It is well known that the resolution method (for propositional logic) is complete. However, completeness proofs found in the literature use an argument by contradiction showing that if a set of clauses is unsatisfiable, then it must have a resolution refutation. As a consequence, none of these proofs actually gives an algorithm for producing a resolution refutation from an unsatisfiable set of clauses. In this note, we give a simple and constructive proof of the completeness of propositional resolution which consists of an algorithm together with a proof of its correctness.
Breaking barriers for people with voice disabilities: Combining virtual keyboards with speech synthesizers, and VoIP applications
Venue: arXiv cs.CY 2006
Year: 2006

Text-to-speech technology has been broadly used to help people with voice disabilities to overcome their difficulties. With text-to-speech, a person types at a keyboard, the text is synthesized, and the sound comes out through the computer speakers. In recent years, Voice over IP (VoIP) applications have become very popular and have been used by people worldwide. These applications allow people to talk for free over the Internet and also to make traditional calls through the Public-Switched Telephone Network (PSTN) at a small fraction of the cost offered by traditional phone companies. We have created a system, called EasyVoice, which integrates speech synthesizers with VoIP applications. The result allows a person with motor impairments and voice disabilities to talk with another person located anywhere in the world. The benefits in this case are much stronger than the ones obtained by non-disabled people using VoIP applications. People with motor impairments sometimes can hardly use a regular or mobile phone. Thus, the advantage is not only the reduction in cost, but more important, the ability to talk at all.
NVision-PA: A Tool for Visual Analysis of Command Behavior Based on Process Accounting Logs (with a Case Study in HPC Cluster Security)
Venue: arXiv cs.CR 2006
Year: 2006

In the UNIX/Linux environment the kernel can log every command process created by every user with process accounting. Thus process accounting logs have many potential uses, particularly the monitoring and forensic investigation of security events. Previous work successfully leveraged the use of process accounting logs to identify a difficult to detect and damaging intrusion against high performance computing (HPC) clusters, masquerade attacks, where intruders masquerade as legitimate users with purloined authentication credentials. While masqueraders on HPC clusters were found to be identifiable with a high accuracy (greater than 90%), this accuracy is still not high enough for HPC production environments where greater than 99% accuracy is needed. This paper incrementally advances the goal of more accurately identifying masqueraders on HPC clusters by seeking to identify features within command sets that distinguish masqueraders. To accomplish this goal, we created NVision-PA, a software tool that produces text and graphic statistical summaries describing input processing accounting logs. We report NVision-PA results describing two different process accounting logs; one from Internet usage and one from HPC cluster usage. These results identify the distinguishing features of Internet users (as proxies for masqueraders) posing as clusters users. This research is both a promising next step toward creating a real-time masquerade detection sensor for production HPC clusters as well as providing another tool for system administrators to use for statistically monitoring and managing legitimate workloads (as indicated by command usage) in HPC environments.
Error Rate Analysis for Coded Multicarrier Systems over Quasi-Static Fading Channels
Venue: arXiv cs.IT 2006
Year: 2006

Several recent standards such as IEEE 802.11a/g, IEEE 802.16, and ECMA Multiband Orthogonal Frequency Division Multiplexing (MB-OFDM) for high data-rate Ultra-Wideband (UWB), employ bit-interleaved convolutionally-coded multicarrier modulation over quasi-static fading channels. Motivated by the lack of appropriate error rate analysis techniques for this popular type of system and channel model, we present two novel analytical methods for bit error rate (BER) estimation of coded multicarrier systems operating over frequency-selective quasi-static channels with non-ideal interleaving. In the first method, the approximate performance of the system is calculated for each realization of the channel, which is suitable for obtaining the outage BER performance (a common performance measure for e.g. MB-OFDM systems). The second method assumes Rayleigh distributed frequency-domain subcarrier channel gains and knowledge of their correlation matrix, and can be used to directly obtain the average BER performance. Both methods are applicable to convolutionally-coded interleaved multicarrier systems employing Quadrature Amplitude Modulation (QAM), and are also able to account for narrowband interference (modeled as a sum of tone interferers). To illustrate the application of the proposed analysis, both methods are used to study the performance of a tone-interference-impaired MB-OFDM system.
Stochastic Formal Methods: An application to accuracy of numeric software
Venue: arXiv cs.MS 2006
Year: 2006

This paper provides a bound on the number of numeric operations (fixed or floating point) that can safely be performed before accuracy is lost. This work has important implications for control systems with safety-critical software, as these systems are now running fast enough and long enough for their errors to impact on their functionality. Furthermore, worst-case analysis would blindly advise the replacement of existing systems that have been successfully running for years. We present here a set of formal theorems validated by the PVS proof assistant. These theorems will allow code analyzing tools to produce formal certificates of accurate behavior. For example, FAA regulations for aircraft require that the probability of an error be below $10^{-9}$ for a 10 hour flight.
Iso9000 Based Advanced Quality Approach for Continuous Improvement of Manufacturing Processes
Venue: arXiv cs.IR 2006
Year: 2006

The continuous improvement in TQM is considered as the core value by which organisation could maintain a competitive edge. Several techniques and tools are known to support this core value but most of the time these techniques are informal and without modelling the interdependence between the core value and tools. Thus, technique formalisation is one of TQM challenges for increasing efficiency of quality process implementation. In that way, the paper proposes and experiments an advanced quality modelling approach based on meta-modelling the "process approach" as advocated by the standard ISO9000:2000. This meta-model allows formalising the interdependence between technique, tools and core value
Human Information Processing with the Personal Memex
Venue: arXiv cs.HC 2006
Year: 2006

In this report, we describe the work done in a project that explored the human information processing aspects of a personal memex (a memex to organize personal information). In the project, we considered the use of the personal memex, focusing on information recall, by three populations: people with Mild Cognitive Impairment, those diagnosed with Macular Degeneration, and a high-functioning population. The outcomes of the project included human information processing-centered design guidelines for the memex interface, a low-fidelity prototype, and an annotated bibliography for human information processing, usability and design literature relating to the memex and the populations we explored.
A Product Oriented Modelling Concept: Holons for systems synchronisation and interoperability
Venue: arXiv cs.SE 2006
Year: 2006

Nowadays, enterprises are confronted to growing needs for traceability, product genealogy and product life cycle management. To meet those needs, the enterprise and applications in the enterprise environment have to manage flows of information that relate to flows of material and that are managed in shop floor level. Nevertheless, throughout product lifecycle coordination needs to be established between reality in the physical world (physical view) and the virtual world handled by manufacturing information systems (informational view). This paper presents the "Holon" modelling concept as a means for the synchronisation of both physical view and informational views. Afterwards, we show how the concept of holon can play a major role in ensuring interoperability in the enterprise context.
Use MPLS in Lan's
Venue: arXiv cs.NI 2006
Year: 2006

To demonstrate the result of researches in laboratory with the focus in exhibiting the real impact of the use of the technology MPLS in LAN. Through these researches we will verify that the investment in this technology is shown, of the point of view cost/benefit, very interesting, being necessary, however, the adoption of another measured, in order to settle down a satisfactory level in the items Quality and safety in the sending of packages in VPN but assisting to the requirement latency of the net very well being shown in the tests that it consumes on average one Tuesday leaves of the time spend for the same function in routing IP.
Formalizing typical crosscutting concerns
Venue: arXiv cs.SE 2006
Year: 2006

We present a consistent system for referring crosscutting functionality, relating crosscutting concerns to specific implementation idioms, and formalizing their underlying relations through queries. The system is based on generic crosscutting concerns that we organize and describe in a catalog. We have designed and implemented a tool support for querying source code for instances of the proposed generic concerns and organizing them in composite concern models. The composite concern model adds a new dimension to the dominant decomposition of the system for describing and making explicit source code relations specific to crosscutting concerns implementations. We use the proposed approach to describe crosscutting concerns in design patterns and apply the tool to an opensource system (JHotDraw).
Tightened Upper Bounds on the ML Decoding Error Probability of Binary Linear Block Codes
Venue: arXiv cs.IT 2006
Year: 2006

The performance of maximum-likelihood (ML) decoded binary linear block codes is addressed via the derivation of tightened upper bounds on their decoding error probability. The upper bounds on the block and bit error probabilities are valid for any memoryless, binary-input and output-symmetric communication channel, and their effectiveness is exemplified for various ensembles of turbo-like codes over the AWGN channel. An expurgation of the distance spectrum of binary linear block codes further tightens the resulting upper bounds.
Applying and Combining Three Different Aspect Mining Techniques
Venue: arXiv cs.SE 2006
Year: 2006

Understanding a software system at source-code level requires understanding the different concerns that it addresses, which in turn requires a way to identify these concerns in the source code. Whereas some concerns are explicitly represented by program entities (like classes, methods and variables) and thus are easy to identify, crosscutting concerns are not captured by a single program entity but are scattered over many program entities and are tangled with the other concerns. Because of their crosscutting nature, such crosscutting concerns are difficult to identify, and reduce the understandability of the system as a whole. In this paper, we report on a combined experiment in which we try to identify crosscutting concerns in the JHotDraw framework automatically. We first apply three independently developed aspect mining techniques to JHotDraw and evaluate and compare their results. Based on this analysis, we present three interesting combinations of these three techniques, and show how these combinations provide a more complete coverage of the detected concerns as compared to the original techniques individually. Our results are a first step towards improving the understandability of a system that contains crosscutting concerns, and can be used as a basis for refactoring the identified crosscutting concerns into aspects.
A Quasi-Optimal Leader Election Algorithm in Radio Networks with Log-Logarithmic Awake Time Slots
Venue: arXiv cs.DC 2006
Year: 2006

Radio networks (RN) are distributed systems (\textit{ad hoc networks}) consisting in $n \ge 2$ radio stations. Assuming the number $n$ unknown, two distinct models of RN without collision detection (\textit{no-CD}) are addressed: the model with \textit{weak no-CD} RN and the one with \textit{strong no-CD} RN. We design and analyze two distributed leader election protocols, each one running in each of the above two (no-CD RN) models, respectively. Both randomized protocols are shown to elect a leader within $\BO(\log{(n)})$ expected time, with no station being awake for more than $\BO(\log{\log{(n)}})$ time slots (such algorithms are said to be \textit{energy-efficient}). Therefore, a new class of efficient algorithms is set up that matchthe $Ω(\log{(n)})$ time lower-bound established by Kushilevitz and Mansour.
Methods for Partitioning Data to Improve Parallel Execution Time for Sorting on Heterogeneous Clusters
Venue: arXiv cs.DC 2006
Year: 2006

The aim of the paper is to introduce general techniques in order to optimize the parallel execution time of sorting on a distributed architectures with processors of various speeds. Such an application requires a partitioning step. For uniformly related processors (processors speeds are related by a constant factor), we develop a constant time technique for mastering processor load and execution time in an heterogeneous environment and also a technique to deal with unknown cost functions. For non uniformly related processors, we use a technique based on dynamic programming. Most of the time, the solutions are in O(p) (p is the number of processors), independent of the problem size n. Consequently, there is a small overhead regarding the problem we deal with but it is inherently limited by the knowing of time complexity of the portion of code following the partitioning.
Improved online hypercube packing
Venue: arXiv cs.DS 2006
Year: 2006

In this paper, we study online multidimensional bin packing problem when all items are hypercubes. Based on the techniques in one dimensional bin packing algorithm Super Harmonic by Seiden, we give a framework for online hypercube packing problem and obtain new upper bounds of asymptotic competitive ratios. For square packing, we get an upper bound of 2.1439, which is better than 2.24437. For cube packing, we also give a new upper bound 2.6852 which is better than 2.9421 by Epstein and van Stee.
Reasoning with Intervals on Granules
Venue: arXiv cs.AI 2006
Year: 2006

The formalizations of periods of time inside a linear model of Time are usually based on the notion of intervals, that may contain or may not their endpoints. This is not enought when the periods are written in terms of coarse granularities with respect to the event taken into account. For instance, how to express the inter-war period in terms of a {\em years} interval? This paper presents a new type of intervals, neither open, nor closed or open-closed and the extension of operations on intervals of this new type, in order to reduce the gap between the discourse related to temporal relationship and its translation into a discretized model of Time.
Decomposable Theories
Venue: arXiv cs.LO 2006
Year: 2006

We present in this paper a general algorithm for solving first-order formulas in particular theories called "decomposable theories". First of all, using special quantifiers, we give a formal characterization of decomposable theories and show some of their properties. Then, we present a general algorithm for solving first-order formulas in any decomposable theory "T". The algorithm is given in the form of five rewriting rules. It transforms a first-order formula "P", which can possibly contain free variables, into a conjunction "Q" of solved formulas easily transformable into a Boolean combination of existentially quantified conjunctions of atomic formulas. In particular, if "P" has no free variables then "Q" is either the formula "true" or "false". The correctness of our algorithm proves the completeness of the decomposable theories. Finally, we show that the theory "Tr" of finite or infinite trees is a decomposable theory and give some benchmarks realized by an implementation of our algorithm, solving formulas on two-partner games in "Tr" with more than 160 nested alternated quantifiers.
Counting good truth assignments of random k-SAT formulae
Venue: arXiv cs.DM 2006
Year: 2006

We present a deterministic approximation algorithm to compute logarithm of the number of `good' truth assignments for a random k-satisfiability (k-SAT) formula in polynomial time (by `good' we mean that violate a small fraction of clauses). The relative error is bounded above by an arbitrarily small constant epsilon with high probability as long as the clause density (ratio of clauses to variables) alpha<alpha_{u}(k) = 2k^{-1}\log k(1+o(1)). The algorithm is based on computation of marginal distribution via belief propagation and use of an interpolation procedure. This scheme substitutes the traditional one based on approximation of marginal probabilities via MCMC, in conjunction with self-reduction, which is not easy to extend to the present problem. We derive 2k^{-1}\log k (1+o(1)) as threshold for uniqueness of the Gibbs distribution on satisfying assignment of random infinite tree k-SAT formulae to establish our results, which is of interest in its own right.
Neural Networks with Complex and Quaternion Inputs
Venue: arXiv cs.NE 2006
Year: 2006

This article investigates Kak neural networks, which can be instantaneously trained, for complex and quaternion inputs. The performance of the basic algorithm has been analyzed and shown how it provides a plausible model of human perception and understanding of images. The motivation for studying quaternion inputs is their use in representing spatial rotations that find applications in computer graphics, robotics, global navigation, computer vision and the spatial orientation of instruments. The problem of efficient mapping of data in quaternion neural networks is examined. Some problems that need to be addressed before quaternion neural networks find applications are identified.
Properties of subspace subcodes of optimum codes in rank metric
Venue: arXiv cs.IT 2006
Year: 2006

Maximum rank distance codes denoted MRD-codes are the equivalent in rank metric of MDS-codes. Given any integer $q$ power of a prime and any integer $n$ there is a family of MRD-codes of length $n$ over $\FF{q^n}$ having polynomial-time decoding algorithms. These codes can be seen as the analogs of Reed-Solomon codes (hereafter denoted RS-codes) for rank metric. In this paper their subspace subcodes are characterized. It is shown that hey are equivalent to MRD-codes constructed in the same way but with smaller parameters. A specific polynomial-time decoding algorithm is designed. Moreover, it is shown that the direct sum of subspace subcodes is equivalent to the direct product of MRD-codes with smaller parameters. This implies that the decoding procedure can correct errors of higher rank than the error-correcting capability. Finally it is shown that, for given parameters, subfield subcodes are completely characterized by elements of the general linear group ${GL}_n(\FF{q})$ of non-singular $q$-ary matrices of size $n$.
Enterprise Content Management: Theory and Engineering for Entire Lifecycle Support
Venue: arXiv cs.SE 2006
Year: 2006

The paper considers enterprise content management (ECM) issues in global heterogeneous distributed computational environment. Present-day enterprises have accumulated a huge data burden. Manipulating with such a bulk becomes an essential problem, particularly due to its global distribution, heterogeneous and weak-structured character. The conceptual approach to integrated ECM lifecycle support is presented, including overview of formal models, software development methodology and innovative software development tools. Implementation results proved shortening terms and reducing costs of implementation compared to commercial software available.
Abstract Machine as a Model of Content Management Information System
Venue: arXiv cs.SE 2006
Year: 2006

Enterprise content management is an urgent issue of current scientific and practical activities in software design and implementation. However, papers known as yet give insufficient coverage of theoretical background of the software in question. The paper gives an attempt of building a state-based model of content management. In accordance with the theoretical principles outlined, a content management information system (CMIS) has been implemented in a large international oil-and-gas group of companies.