OpenRaiser/Intern-Atlas huggingface dataset:
Bijective Faithful Translations among Default Logics
Venue: arXiv cs.AI 2007
Year: 2007

In this article, we study translations between variants of defaults logics such that the extensions of the theories that are the input and the output of the translation are in a bijective correspondence. We assume that a translation can introduce new variables and that the result of translating a theory can either be produced in time polynomial in the size of the theory or its output is polynomial in that size; we however restrict to the case in which the original theory has extensions. This study fills a gap between two previous pieces of work, one studying bijective translations among restrictions of default logics, and the other one studying non-bijective translations between default logics variants.
Interactive Small-Step Algorithms I: Axiomatization
Venue: arXiv cs.LO 2007
Year: 2007

In earlier work, the Abstract State Machine Thesis -- that arbitrary algorithms are behaviorally equivalent to abstract state machines -- was established for several classes of algorithms, including ordinary, interactive, small-step algorithms. This was accomplished on the basis of axiomatizations of these classes of algorithms. Here we extend the axiomatization and, in a companion paper, the proof, to cover interactive small-step algorithms that are not necessarily ordinary. This means that the algorithms (1) can complete a step without necessarily waiting for replies to all queries from that step and (2) can use not only the environment's replies but also the order in which the replies were received.
One-way Hash Function Based on Neural Network
Venue: arXiv cs.CR 2007
Year: 2007

A hash function is constructed based on a three-layer neural network. The three neuron-layers are used to realize data confusion, diffusion and compression respectively, and the multi-block hash mode is presented to support the plaintext with variable length. Theoretical analysis and experimental results show that this hash function is one-way, with high key sensitivity and plaintext sensitivity, and secure against birthday attacks or meet-in-the-middle attacks. Additionally, the neural network's property makes it practical to realize in a parallel way. These properties make it a suitable choice for data signature or authentication.
Services within a busy period of an M/M/1 queue and Dyck paths
Venue: arXiv cs.DM 2007
Year: 2007

We analyze the service times of customers in a stable M/M/1 queue in equilibrium depending on their position in a busy period. We give the law of the service of a customer at the beginning, at the end, or in the middle of the busy period. It enables as a by-product to prove that the process of instants of beginning of services is not Poisson. We then proceed to a more precise analysis. We consider a family of polynomial generating series associated with Dyck paths of length 2n and we show that they provide the correlation function of the successive services in a busy period with (n+1) customers.
On Throughput Scaling of Wireless Networks: Effect of Node Density and Propagation Model
Venue: arXiv cs.IT 2007
Year: 2007

This paper derives a lower bound to the per-node throughput achievable by a wireless network when n source-destination pairs are randomly distributed throughout a disk of radius $n^γ$, $ γ\geq 0$, propagation is modeled by attenuation of the form $1/(1+d)^α$, $α>2$, and successful transmission occurs at a fixed rate W when received signal to noise and interference ratio is greater than some threshold $β$, and at rate 0 otherwise. The lower bound has the form $n^{1-γ}$ when $γ< 1/2$, and $(n \ln n)^{-1/2}$ when $γ\geq 1/2$. The methods are similar to, but somewhat simpler than, those in the seminal paper by Gupta and Kumar.
Communication under Strong Asynchronism
Venue: arXiv cs.IT 2007
Year: 2007

We consider asynchronous communication over point-to-point discrete memoryless channels. The transmitter starts sending one block codeword at an instant that is uniformly distributed within a certain time period, which represents the level of asynchronism. The receiver, by means of a sequential decoder, must isolate the message without knowing when the codeword transmission starts but being cognizant of the asynchronism level A. We are interested in how quickly can the receiver isolate the sent message, particularly in the regime where A is exponentially larger than the codeword length N, which we refer to as `strong asynchronism.' This model of sparse communication may represent the situation of a sensor that remains idle most of the time and, only occasionally, transmits information to a remote base station which needs to quickly take action. The first result shows that vanishing error probability can be guaranteed as N tends to infinity while A grows as Exp(N*k) if and only if k does not exceed the `synchronization threshold,' a constant that admits a simple closed form expression, and is at least as large as the capacity of the synchronized channel. The second result is the characterization of a set of achievable strictly positive rates in the regime where A is exponential in N, and where the rate is defined with respect to the expected delay between the time information starts being emitted until the time the receiver makes a decision. As an application of the first result we consider antipodal signaling over a Gaussian channel and derive a simple necessary condition between A, N, and SNR for achieving reliable communication.
Diversity of MIMO Multihop Relay Channels
Venue: arXiv cs.IT 2007
Year: 2007

We consider slow fading relay channels with a single multi-antenna source-destination terminal pair. The source signal arrives at the destination via N hops through N-1 layers of relays. We analyze the diversity of such channels with fixed network size at high SNR. In the clustered case where the relays within the same layer can have full cooperation, the cooperative decode-and-forward (DF) scheme is shown to be optimal in terms of the diversity-multiplexing tradeoff (DMT). The upper bound on the DMT, the cut-set bound, is attained. In the non-clustered case, we show that the naive amplify-and-forward (AF) scheme has the maximum multiplexing gain of the channel but is suboptimal in diversity, as compared to the cut-set bound. To improve the diversity, space-time relay processing is introduced through the parallel partition of the multihop channel. The idea is to let the source signal go through K different "AF paths" in the multihop channel. This parallel AF scheme creates a parallel channel in the time domain and has the maximum diversity if the partition is properly designed. Since this scheme does not achieve the maximum multiplexing gain in general, we propose a flip-and-forward (FF) scheme that is built from the parallel AF scheme. It is shown that the FF scheme achieves both the maximum diversity and multiplexing gains in a distributed multihop channel of arbitrary size. In order to realize the DMT promised by the relaying strategies, approximately universal coding schemes are also proposed.
Virtual Manufacturing : Tools for improving Design and Production
Venue: arXiv cs.RO 2007
Year: 2007

The research area "Virtual Manufacturing" can be defined as an integrated manufacturing environment which can enhance one or several levels of decision and control in manufacturing process. Several domains can be addressed: Product and Process Design, Process and Production Planning, Machine Tool, Robot and Manufacturing System. As automation technologies such as CAD/CAM have substantially shortened the time required to design products, Virtual Manufacturing will have a similar effect on the manufacturing phase thanks to the modelling, simulation and optimisation of the product and the processes involved in its fabrication.
Introducing OPTO : Portal for Optical Communities in Indonesia
Venue: arXiv cs.CY 2007
Year: 2007

Since January 1, 2005 we have launched "OPTO" Portal, a website dedicated to optical communities in Indonesia. The address of this portal is http://www.opto.lipi.go.id and is self-supporting managed and not for commercial purposes. Our aims in launching this portal are to benefit Internet facility in increasing the communities' scientific activity; to provide an online reference in Indonesian language for optics-based science and technology subjects; as well as to pioneer the communities' online activities with real impacts and benefits for our society. We will describe in the paper the features of this portal that can be utilized by all individuals or members of optical communities to store and share information and to build networks or partnership as well. We realized that this portal is still not popular and most of our aims are still not reached. This conference should be a good place for all of us to collaborate to properly utilize this portal for the advantages to the optical communities in Indonesia and our society at large.
Real-time control and monitoring system for LIPI's Public Cluster
Venue: arXiv cs.DC 2007
Year: 2007

We have developed a monitoring and control system for LIPI's Public Cluster. The system consists of microcontrollers and full web-based user interfaces for daily operation. It is argued that, due to its special natures, the cluster requires fully dedicated and self developed control and monitoring system. We discuss the implementation of using parallel port and dedicated micro-controller for this purpose. We also show that integrating such systems enables an autonomous control system based on the real time monitoring, for instance an autonomous power supply control based on the actual temperature, etc.
Resource Allocation in Public Cluster with Extended Optimization Algorithm
Venue: arXiv cs.DC 2007
Year: 2007

We introduce an optimization algorithm for resource allocation in the LIPI Public Cluster to optimize its usage according to incoming requests from users. The tool is an extended and modified genetic algorithm developed to match specific natures of public cluster. We present a detail analysis of optimization, and compare the results with the exact calculation. We show that it would be very useful and could realize an automatic decision making system for public clusters.
Auction-Based Distributed Resource Allocation for Cooperation Transmission in Wireless Networks
Venue: arXiv cs.IT 2007
Year: 2007

Cooperative transmission can greatly improve communication system performance by taking advantage of the broadcast nature of wireless channels. Most previous work on resource allocation for cooperation transmission is based on centralized control. In this paper, we propose two share auction mechanisms, the SNR auction and the power auction, to distributively coordinate the resource allocation among users. We prove the existence, uniqueness and effectiveness of the auction results. In particular, the SNR auction leads to a fair resource allocation among users, and the power auction achieves a solution that is close to the efficient allocation.
A Matrix Ring Description for Cyclic Convolutional Codes
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, we study convolutional codes with a specific cyclic structure. By definition, these codes are left ideals in a certain skew polynomial ring. Using that the skew polynomial ring is isomorphic to a matrix ring we can describe the algebraic parameters of the codes in a more accessible way. We show that the existence of such codes with given algebraic parameters can be reduced to the solvability of a modified rook problem. It is our strong belief that the rook problem is always solvable, and we present solutions in particular cases.
MIMO-OFDM Optimal Decoding and Achievable Information Rates Under Imperfect Channel Estimation
Venue: arXiv cs.NI 2007
Year: 2007

Optimal decoding of bit interleaved coded modulation (BICM) MIMO-OFDM where an imperfect channel estimate is available at the receiver is investigated. First, by using a Bayesian approach involving the channel a posteriori density, we derive a practical decoding metric for general memoryless channels that is robust to the presence of channel estimation errors. Then, we evaluate the outage rates achieved by a decoder that uses our proposed metric. The performance of the proposed decoder is compared to the classical mismatched decoder and a theoretical decoder defined as the best decoder in the presence of imperfect channel estimation. Numerical results over Rayleigh block fading MIMO-OFDM channels show that the proposed decoder outperforms mismatched decoding in terms of bit error rate and outage capacity without introducing any additional complexity.
Resolution over Linear Equations and Multilinear Proofs
Venue: arXiv cs.CC 2007
Year: 2007

We develop and study the complexity of propositional proof systems of varying strength extending resolution by allowing it to operate with disjunctions of linear equations instead of clauses. We demonstrate polynomial-size refutations for hard tautologies like the pigeonhole principle, Tseitin graph tautologies and the clique-coloring tautologies in these proof systems. Using the (monotone) interpolation by a communication game technique we establish an exponential-size lower bound on refutations in a certain, considerably strong, fragment of resolution over linear equations, as well as a general polynomial upper bound on (non-monotone) interpolants in this fragment. We then apply these results to extend and improve previous results on multilinear proofs (over fields of characteristic 0), as studied in [RazTzameret06]. Specifically, we show the following: 1. Proofs operating with depth-3 multilinear formulas polynomially simulate a certain, considerably strong, fragment of resolution over linear equations. 2. Proofs operating with depth-3 multilinear formulas admit polynomial-size refutations of the pigeonhole principle and Tseitin graph tautologies. The former improve over a previous result that established small multilinear proofs only for the \emph{functional} pigeonhole principle. The latter are different than previous proofs, and apply to multilinear proofs of Tseitin mod p graph tautologies over any field of characteristic 0. We conclude by connecting resolution over linear equations with extensions of the cutting planes proof system.
A nearly tight memory-redundancy trade-off for one-pass compression
Venue: arXiv cs.IT 2007
Year: 2007

Let $s$ be a string of length $n$ over an alphabet of constant size $σ$ and let $c$ and $ε$ be constants with (1 \geq c \geq 0) and (ε> 0). Using (O (n)) time, (O (n^c)) bits of memory and one pass we can always encode $s$ in (n H_k (s) + O (σ^k n^{1 - c + ε})) bits for all integers (k \geq 0) simultaneously. On the other hand, even with unlimited time, using (O (n^c)) bits of memory and one pass we cannot always encode $s$ in (O (n H_k (s) + σ^k n^{1 - c - ε})) bits for, e.g., (k = \lceil (c + ε/ 2) \log_σn \rceil).
Repairing Inconsistent XML Write-Access Control Policies
Venue: arXiv cs.DB 2007
Year: 2007

XML access control policies involving updates may contain security flaws, here called inconsistencies, in which a forbidden operation may be simulated by performing a sequence of allowed operations. This paper investigates the problem of deciding whether a policy is consistent, and if not, how its inconsistencies can be repaired. We consider policies expressed in terms of annotated DTDs defining which operations are allowed or denied for the XML trees that are instances of the DTD. We show that consistency is decidable in PTIME for such policies and that consistent partial policies can be extended to unique "least-privilege" consistent total policies. We also consider repair problems based on deleting privileges to restore consistency, show that finding minimal repairs is NP-complete, and give heuristics for finding repairs.
Capacity of the Degraded Half-Duplex Relay Channel
Venue: arXiv cs.IT 2007
Year: 2007

A discrete memoryless half-duplex relay channel is constructed from a broadcast channel from the source to the relay and destination and a multiple access channel from the source and relay to the destination. When the relay listens, the channel operates in the broadcast mode. The channel switches to the multiple access mode when the relay transmits. If the broadcast component channel is physically degraded, the half-duplex relay channel will also be referred to as physically degraded. The capacity of this degraded half-duplex relay channel is examined. It is shown that the block Markov coding suggested in the seminal paper by Cover and El Gamal can be modified to achieve capacity for the degraded half-duplex relay channel. In the code construction, the listen-transmit schedule of the relay is made to depend on the message to be sent and hence the schedule carries information itself. If the schedule is restricted to be deterministic, it is shown that the capacity can be achieved by a simple management of information flows across the broadcast and multiple access component channels.
Question on Conditional Entropy
Venue: arXiv cs.IT 2007
Year: 2007

The problems of conditional entropy's definition and the formula to compute conditional entropy are analyzed from various perspectives, and the corrected computing formula is presented. Examples are given to prove the conclusion that conditional entropy never be increased is not absolute, thus the representation that information is to decrease uncertainty in the definition of information is not absolutely correct.
Web Server Benchmark Application WiiBench using Erlang/OTP R11 and Fedora-Core Linux 5.0
Venue: arXiv cs.NI 2007
Year: 2007

As the web grows and the amount of traffics on the web server increase, problems related to performance begin to appear. Some of the problems, such as the number of users that can access the server simultaneously, the number of requests that can be handled by the server per second (requests per second) to bandwidth consumption and hardware utilization like memories and CPU. To give better quality of service (\textbf{\textit{QoS}}), web hosting providers and also the system administrators and network administrators who manage the server need a benchmark application to measure the capabilities of their servers. Later, the application intends to work under Linux/Unix -- like platforms and built using Erlang/OTP R11 as a concurrent oriented language under Fedora Core Linux 5.0. \textbf{\textit{WiiBench}} is divided into two main parts, the controller section and the launcher section. Controller is the core of the application. It has several duties, such as read the benchmark scenario file, configure the program based on the scenario, initialize the launcher section, gather the benchmark results from local and remote Erlang node where the launcher runs and write them in a log file (later the log file will be used to generate a report page for the sysadmin). Controller also has function as a timer which act as timing for user inters arrival to the server. Launcher generates a number of users based on the scenario, initialize them and start the benchmark by sending requests to the web server. The clients also gather the benchmark result and send them to the controller.
The Frobenius Problem in a Free Monoid
Venue: arXiv cs.DM 2007
Year: 2007

The classical Frobenius problem is to compute the largest number g not representable as a non-negative integer linear combination of non-negative integers x_1, x_2, ..., x_k, where gcd(x_1, x_2, ..., x_k) = 1. In this paper we consider generalizations of the Frobenius problem to the noncommutative setting of a free monoid. Unlike the commutative case, where the bound on g is quadratic, we are able to show exponential or subexponential behavior for an analogue of g, depending on the particular measure chosen.
A Neural Networks Model of the Venezuelan Economy
Venue: arXiv cs.CE 2007
Year: 2007

Besides an indicator of the GDP, the Central Bank of Venezuela generates the so called Monthly Economic Activity General Indicator. The a priori knowledge of this indicator, which represents and sometimes even anticipates the economy's fluctuations, could be helpful in developing public policies and in investment decision making. The purpose of this study is forecasting the IGAEM through non parametric methods, an approach that has proven effective in a wide variety of problems in economics and finance.
HORPO with Computability Closure : A Reconstruction
Venue: arXiv cs.LO 2007
Year: 2007

This paper provides a new, decidable definition of the higher- order recursive path ordering in which type comparisons are made only when needed, therefore eliminating the need for the computability clo- sure, and bound variables are handled explicitly, making it possible to handle recursors for arbitrary strictly positive inductive types.
Parametric stiffness analysis of the Orthoglide
Venue: arXiv cs.RO 2007
Year: 2007

This paper presents a parametric stiffness analysis of the Orthoglide. A compliant modeling and a symbolic expression of the stiffness matrix are conducted. This allows a simple systematic analysis of the influence of the geometric design parameters and to quickly identify the critical link parameters. Our symbolic model is used to display the stiffest areas of the workspace for a specific machining task. Our approach can be applied to any parallel manipulator for which stiffness is a critical issue.
On the complexity of nonnegative matrix factorization
Venue: arXiv cs.NA 2007
Year: 2007

Nonnegative matrix factorization (NMF) has become a prominent technique for the analysis of image databases, text databases and other information retrieval and clustering applications. In this report, we define an exact version of NMF. Then we establish several results about exact NMF: (1) that it is equivalent to a problem in polyhedral combinatorics; (2) that it is NP-hard; and (3) that a polynomial-time local search heuristic exists.
Algebraic Distributed Differential Space-Time Codes with Low Decoding Complexity
Venue: arXiv cs.IT 2007
Year: 2007

The differential encoding/decoding setup introduced by Kiran et al, Oggier-Hassibi and Jing-Jafarkhani for wireless relay networks that use codebooks consisting of unitary matrices is extended to allow codebooks consisting of scaled unitary matrices. For such codebooks to be usable in the Jing-Hassibi protocol for cooperative diversity, the conditions involving the relay matrices and the codebook that need to be satisfied are identified. Using the algebraic framework of extended Clifford algebras, a new class of Distributed Differential Space-Time Codes satisfying these conditions for power of two number of relays and also achieving full cooperative diversity with a low complexity sub-optimal receiver is proposed. Simulation results indicate that the proposed codes outperform both the cyclic codes as well as the circulant codes. Furthermore, these codes can also be applied as Differential Space-Time codes for non-coherent communication in classical point to point multiple antenna systems.
Estimating Random Variables from Random Sparse Observations
Venue: arXiv cs.IT 2007
Year: 2007

Let X_1,...., X_n be a collection of iid discrete random variables, and Y_1,..., Y_m a set of noisy observations of such variables. Assume each observation Y_a to be a random function of some a random subset of the X_i's, and consider the conditional distribution of X_i given the observations, namely μ_i(x_i)\equiv\prob\{X_i=x_i|Y\} (a posteriori probability). We establish a general relation between the distribution of μ_i, and the fixed points of the associated density evolution operator. Such relation holds asymptotically in the large system limit, provided the average number of variables an observation depends on is bounded. We discuss the relevance of our result to a number of applications, ranging from sparse graph codes, to multi-user detection, to group testing.