OpenRaiser/Intern-Atlas huggingface dataset:
A Recursive Method for Determining the One-Dimensional Submodules of Laurent-Ore Modules
Venue: arXiv cs.SC 2006
Year: 2006

We present a method for determining the one-dimensional submodules of a Laurent-Ore module. The method is based on a correspondence between hyperexponential solutions of associated systems and one-dimensional submodules. The hyperexponential solutions are computed recursively by solving a sequence of first-order ordinary matrix equations. As the recursion proceeds, the matrix equations will have constant coefficients with respect to the operators that have been considered.
Simplicial models of social aggregation I
Venue: arXiv cs.CE 2006
Year: 2006

This paper presents the foundational ideas for a new way of modeling social aggregation. Traditional approaches have been using network theory, and the theory of random networks. Under that paradigm, every social agent is represented by a node, and every social interaction is represented by a segment connecting two nodes. Early work in family interactions, as well as more recent work in the study of terrorist organizations, shows that network modeling may be insufficient to describe the complexity of human social structures. Specifically, network theory does not seem to have enough flexibility to represent higher order aggregations, where several agents interact as a group, rather than as a collection of pairs. The model we present here uses a well established mathematical theory, the theory of simplicial complexes, to address this complex issue prevalent in interpersonal and intergroup communication. The theory enables us to provide a richer graphical representation of social interactions, and to determine quantitative mechanisms to describe the robustness of a social structure. We also propose a methodology to create random simplicial complexes, with the purpose of providing a new method to simulate computationally the creation and disgregation of social structures. Finally, we propose several measures which could be taken and observed in order to describe and study an actual social aggregation occurring in interpersonal and intergroup contexts.
Robust Distributed Source Coding
Venue: arXiv cs.IT 2006
Year: 2006

We consider a distributed source coding system in which several observations are communicated to the decoder using limited transmission rate. The observations must be separately coded. We introduce a robust distributed coding scheme which flexibly trades off between system robustness and compression efficiency. The optimality of this coding scheme is proved for various special cases.
Fixed-Parameter Complexity of Minimum Profile Problems
Venue: arXiv cs.DS 2006
Year: 2006

Let $G=(V,E)$ be a graph. An ordering of $G$ is a bijection $α: V\dom \{1,2,..., |V|\}.$ For a vertex $v$ in $G$, its closed neighborhood is $N[v]=\{u\in V: uv\in E\}\cup \{v\}.$ The profile of an ordering $α$ of $G$ is $\prf_α(G)=\sum_{v\in V}(α(v)-\min\{α(u): u\in N[v]\}).$ The profile $\prf(G)$ of $G$ is the minimum of $\prf_α(G)$ over all orderings $α$ of $G$. It is well-known that $\prf(G)$ is the minimum number of edges in an interval graph $H$ that contains $G$ is a subgraph. Since $|V|-1$ is a tight lower bound for the profile of connected graphs $G=(V,E)$, the parametrization above the guaranteed value $|V|-1$ is of particular interest. We show that deciding whether the profile of a connected graph $G=(V,E)$ is at most $|V|-1+k$ is fixed-parameter tractable with respect to the parameter $k$. We achieve this result by reduction to a problem kernel of linear size.
Further Evaluationh of VLEs using HCI and Educational Metrics
Venue: arXiv cs.HC 2006
Year: 2006

Under consideration are the general set of Human computer Interaction (HCI) and Educational principles from prominent authors in the field and the construction of a system for evaluating Virtual Learning Environments (VLEs) with respect to the application of these HCI and Educational Principles. A frequency analysis of principles is used to obtain the most significant set. Metrics are devised to provide objective measures of these principles and a consistent testing regime is introduced. These principles are used to analyse the University VLE Blackboard. An open source VLE is also constructed with similar content to Blackboard courses so that a systematic comparison can be made. HCI and Educational metrics are determined for each VLE.
An Algebraic View of the Relation between Largest Common Subtrees and Smallest Common Supertrees
Venue: arXiv cs.DS 2006
Year: 2006

The relationship between two important problems in tree pattern matching, the largest common subtree and the smallest common supertree problems, is established by means of simple constructions, which allow one to obtain a largest common subtree of two trees from a smallest common supertree of them, and vice versa. These constructions are the same for isomorphic, homeomorphic, topological, and minor embeddings, they take only time linear in the size of the trees, and they turn out to have a clear algebraic meaning.
CMS Software Distribution on the LCG and OSG Grids
Venue: arXiv cs.DC 2006
Year: 2006

The efficient exploitation of worldwide distributed storage and computing resources available in the grids require a robust, transparent and fast deployment of experiment specific software. The approach followed by the CMS experiment at CERN in order to enable Monte-Carlo simulations, data analysis and software development in an international collaboration is presented. The current status and future improvement plans are described.
A Characterization of the Degree Sequences of 2-Trees
Venue: arXiv cs.DM 2006
Year: 2006

A graph G is a 2-tree if G=K_3, or G has a vertex v of degree 2, whose neighbours are adjacent, and Gǐs a 2-tree. A characterization of the degree sequences of 2-trees is given. This characterization yields a linear-time algorithm for recognizing and realizing degree sequences of 2-trees.
A Formal Measure of Machine Intelligence
Venue: arXiv cs.AI 2006
Year: 2006

A fundamental problem in artificial intelligence is that nobody really knows what intelligence is. The problem is especially acute when we need to consider artificial systems which are significantly different to humans. In this paper we approach this problem in the following way: We take a number of well known informal definitions of human intelligence that have been given by experts, and extract their essential features. These are then mathematically formalised to produce a general measure of intelligence for arbitrary machines. We believe that this measure formally captures the concept of machine intelligence in the broadest reasonable sense.
Recognition of expression variant faces using masked log-Gabor features and Principal Component Analysis
Venue: arXiv cs.CV 2006
Year: 2006

In this article we propose a method for the recognition of faces with different facial expressions. For recognition we extract feature vectors by using log-Gabor filters of multiple orientations and scales. Using sliding window algorithm and variances -based masking these features are extracted at image regions that are less affected by the changes of facial expressions. Extracted features are passed to the Principal Component Analysis (PCA) -based recognition method. The results of face recognition experiments using expression variant faces showed that the proposed method could achieve higher recognition accuracy than many other methods. For development and testing we used facial images from the AR and FERET databases. Using facial photographs of more than one thousand persons from the FERET database the proposed method achieved 96.6-98.9% first one recognition rate and 0.2-0.6% Equal Error Rate (EER).
A framework of reusable structures for mobile agent development
Venue: arXiv cs.MA 2006
Year: 2006

Mobile agents research is clearly aiming towards imposing agent based development as the next generation of tools for writing software. This paper comes with its own contribution to this global goal by introducing a novel unifying framework meant to bring simplicity and interoperability to and among agent platforms as we know them today. In addition to this, we also introduce a set of agent behaviors which, although tailored for and from the area of virtual learning environments, are none the less generic enough to be used for rapid, simple, useful and reliable agent deployment. The paper also presents an illustrative case study brought forward to prove the feasibility of our design.
Fast and Generalized Polynomial Time Memory Consistency Verification
Venue: arXiv cs.AR 2006
Year: 2006

The problem of verifying multi-threaded execution against the memory consistency model of a processor is known to be an NP hard problem. However polynomial time algorithms exist that detect almost all failures in such execution. These are often used in practice for microprocessor verification. We present a low complexity and fully parallelized algorithm to check program execution against the processor consistency model. In addition our algorithm is general enough to support a number of consistency models without any degradation in performance. An implementation of this algorithm is currently used in practice to verify processors in the post silicon stage for multiple architectures.
Asymptotically Optimal Multiple-access Communication via Distributed Rate Splitting
Venue: arXiv cs.IT 2006
Year: 2006

We consider the multiple-access communication problem in a distributed setting for both the additive white Gaussian noise channel and the discrete memoryless channel. We propose a scheme called Distributed Rate Splitting to achieve the optimal rates allowed by information theory in a distributed manner. In this scheme, each real user creates a number of virtual users via a power/rate splitting mechanism in the M-user Gaussian channel or via a random switching mechanism in the M-user discrete memoryless channel. At the receiver, all virtual users are successively decoded. Compared with other multiple-access techniques, Distributed Rate Splitting can be implemented with lower complexity and less coordination. Furthermore, in a symmetric setting, we show that the rate tuple achieved by this scheme converges to the maximum equal rate point allowed by the information-theoretic bound as the number of virtual users per real user tends to infinity. When the capacity regions are asymmetric, we show that a point on the dominant face can be achieved asymptotically. Finally, when there is an unequal number of virtual users per real user, we show that differential user rate requirements can be accommodated in a distributed fashion.
A General Method for Finding Low Error Rates of LDPC Codes
Venue: arXiv cs.IT 2006
Year: 2006

This paper outlines a three-step procedure for determining the low bit error rate performance curve of a wide class of LDPC codes of moderate length. The traditional method to estimate code performance in the higher SNR region is to use a sum of the contributions of the most dominant error events to the probability of error. These dominant error events will be both code and decoder dependent, consisting of low-weight codewords as well as non-codeword events if ML decoding is not used. For even moderate length codes, it is not feasible to find all of these dominant error events with a brute force search. The proposed method provides a convenient way to evaluate very low bit error rate performance of an LDPC code without requiring knowledge of the complete error event weight spectrum or resorting to a Monte Carlo simulation. This new method can be applied to various types of decoding such as the full belief propagation version of the message passing algorithm or the commonly used min-sum approximation to belief propagation. The proposed method allows one to efficiently see error performance at bit error rates that were previously out of reach of Monte Carlo methods. This result will provide a solid foundation for the analysis and design of LDPC codes and decoders that are required to provide a guaranteed very low bit error rate performance at certain SNRs.
Ontological Representations of Software Patterns
Venue: arXiv cs.SE 2006
Year: 2006

This paper is based on and advocates the trend in software engineering of extending the use of software patterns as means of structuring solutions to software development problems (be they motivated by best practice or by company interests and policies). The paper argues that, on the one hand, this development requires tools for automatic organisation, retrieval and explanation of software patterns. On the other hand, that the existence of such tools itself will facilitate the further development and employment of patterns in the software development process. The paper analyses existing pattern representations and concludes that they are inadequate for the kind of automation intended here. Adopting a standpoint similar to that taken in the semantic web, the paper proposes that feasible solutions can be built on the basis of ontological representations.
An Internet Framework to Bring Coherence between WAP and HTTP Ensuring Better Mobile Internet Security
Venue: arXiv cs.NI 2006
Year: 2006

To bring coherence between Wireless Access Protocol (WAP) and Hyper Text Transfer Protocol (HTTP), in this paper, we have proposed an enhanced Internet framework, which incorporates a new markup language and a browser compatible with both of the access control protocols. This Markup Language and the browser enables co-existence of both Hyper Text Markup Language (HTML) and Wireless Markup Language (WML) contents in a single source file, whereas the browser incorporates the ability to hold contents compliant with both HTTP and WAP. The proposed framework also bridges the security gap that is present in the existing mobile Internet framework. Keywords: WAP, WML, HTTP, HTML, browser, parser, wireless devices.
On the Capacity of Interference Channels with Degraded Message sets
Venue: arXiv cs.IT 2006
Year: 2006

This paper is motivated by a sensor network on a correlated field where nearby sensors share information, and can thus assist rather than interfere with one another. A special class of two-user Gaussian interference channels (IFCs) is considered where one of the two transmitters knows both the messages to be conveyed to the two receivers (called the IFC with degraded message sets). Both achievability and converse arguments are provided for this scenario for a class of discrete memoryless channels with weak interference. For the case of the Gaussian weak interference channel with degraded message sets, optimality of Gaussian inputs is also shown, resulting in the capacity region of this channel.
SAT Solving for Argument Filterings
Venue: arXiv cs.LO 2006
Year: 2006

This paper introduces a propositional encoding for lexicographic path orders in connection with dependency pairs. This facilitates the application of SAT solvers for termination analysis of term rewrite systems based on the dependency pair method. We address two main inter-related issues and encode them as satisfiability problems of propositional formulas that can be efficiently handled by SAT solving: (1) the combined search for a lexicographic path order together with an \emph{argument filtering} to orient a set of inequalities; and (2) how the choice of the argument filtering influences the set of inequalities that have to be oriented. We have implemented our contributions in the termination prover AProVE. Extensive experiments show that by our encoding and the application of SAT solvers one obtains speedups in orders of magnitude as well as increased termination proving power.
On the Capacity of Fading MIMO Broadcast Channels with Imperfect Transmitter Side-Information
Venue: arXiv cs.IT 2006
Year: 2006

A fading broadcast channel is considered where the transmitter employs two antennas and each of the two receivers employs a single receive antenna. It is demonstrated that even if the realization of the fading is precisely known to the receivers, the high signal-to-noise (SNR) throughput is greatly reduced if, rather than knowing the fading realization \emph{precisely}, the trasmitter only knows the fading realization \emph{approximately}. The results are general and are not limited to memoryless Gaussian fading.
Proof Search in Hajek's Basic Logic
Venue: arXiv cs.LO 2006
Year: 2006

We introduce a proof system for Hajek's logic BL based on a relational hypersequents framework. We prove that the rules of our logical calculus, called RHBL, are sound and invertible with respect to any valuation of BL into a suitable algebra, called omega[0,1]. Refining the notion of reduction tree that arises naturally from RHBL, we obtain a decision algorithm for BL provability whose running time upper bound is 2^O(n), where n is the number of connectives of the input formula. Moreover, if a formula is unprovable, we exploit the constructiveness of a polynomial time algorithm for leaves validity for providing a procedure to build countermodels in omega[0,1]. Finally, since the size of the reduction tree branches is O(n^3), we can describe a polynomial time verification algorithm for BL unprovability.
Single-Symbol-Decodable Differential Space-Time Modulation Based on QO-STBC
Venue: arXiv cs.IT 2006
Year: 2006

We present a novel differential space-time modulation (DSTM) scheme that is single-symbol decodable and can provide full transmit diversity. It is the first known singlesymbol- decodable DSTM scheme not based on Orthogonal STBC (O-STBC), and it is constructed based on the recently proposed Minimum-Decoding-Complexity Quasi-Orthogonal Space-Time Block Code (MDC-QOSTBC). We derive the code design criteria and present systematic methodology to find the solution sets. The proposed DSTM scheme can provide higher code rate than DSTM schemes based on O-STBC. Its decoding complexity is also considerably lower than DSTM schemes based on Sp(2) and double-symbol-decodable QOSTBC, with negligible or slight trade-off in decoding error probability performance.
Circle Formation of Weak Robots and Lyndon Words
Venue: arXiv cs.DC 2006
Year: 2006

A Lyndon word is a non-empty word strictly smaller in the lexicographic order than any of its suffixes, except itself and the empty word. In this paper, we show how Lyndon words can be used in the distributed control of a set of n weak mobile robots. By weak, we mean that the robots are anonymous, memoryless, without any common sense of direction, and unable to communicate in an other way than observation. An efficient and simple deterministic protocol to form a regular n-gon is presented and proven for n prime.
Knowledge Flow Analysis for Security Protocols
Venue: arXiv cs.CR 2006
Year: 2006

Knowledge flow analysis offers a simple and flexible way to find flaws in security protocols. A protocol is described by a collection of rules constraining the propagation of knowledge amongst principals. Because this characterization corresponds closely to informal descriptions of protocols, it allows a succinct and natural formalization; because it abstracts away message ordering, and handles communications between principals and applications of cryptographic primitives uniformly, it is readily represented in a standard logic. A generic framework in the Alloy modelling language is presented, and instantiated for two standard protocols, and a new key management scheme.
A Metadata Registry from Vocabularies UP: The NSDL Registry Project
Venue: arXiv cs.DL 2006
Year: 2006

The NSDL Metadata Registry is designed to provide humans and machines with the means to discover, create, access and manage metadata schemes, schemas, application profiles, crosswalks and concept mappings. This paper describes the general goals and architecture of the NSDL Metadata Registry as well as issues encountered during the first year of the project's implementation.
Attaque algebrique de NTRU a l'aide des vecteurs de Witt
Venue: arXiv cs.CR 2006
Year: 2006

One improves an algebraic attack of NTRU due to Silverman, Smart and Vercauteren; the latter considered the first 2 bits of a Witt vector attached to the research of the secret key; here the first 4 bits are considered, which provides additional equations of degrees 4 and 8.
Memory Aware High-Level Synthesis for Embedded Systems
Venue: arXiv cs.AR 2006
Year: 2006

We introduce a new approach to take into account the memory architecture and the memory mapping in the High- Level Synthesis of Real-Time embedded systems. We formalize the memory mapping as a set of constraints used in the scheduling step. We use a memory mapping file to include those memory constraints in our HLS tool GAUT. Our scheduling algorithm exhibits a relatively low complexity that permits to tackle complex designs in a reasonable time. Finally, we show how to explore, with the help of GAUT, a wide range of solutions, and to reach a good tradeoff between time, power-consumption, and area.
Modeling Aspect Mechanisms: A Top-Down Approach
Venue: arXiv cs.SE 2006
Year: 2006

A plethora of diverse aspect mechanisms exist today, all of which integrate concerns into artifacts that exhibit crosscutting structure. What we lack and need is a characterization of the design space that these aspect mechanisms inhabit and a model description of their weaving processes. A good design space representation provides a common framework for understanding and evaluating existing mechanisms. A well-understood model of the weaving process can guide the implementor of new aspect mechanisms. It can guide the designer when mechanisms implementing new kinds of weaving are needed. It can also help teach aspect-oriented programming (AOP). In this paper we present and evaluate such a model of the design space for aspect mechanisms and their weaving processes. We model weaving, at an abstract level, as a concern integration process. We derive a weaving process model (WPM) top-down, differentiating a reactive from a nonreactive process. The model provides an in-depth explanation of the key subpro existing aspect mechanisms.
Repository Replication Using NNTP and SMTP
Venue: arXiv cs.DL 2006
Year: 2006

We present the results of a feasibility study using shared, existing, network-accessible infrastructure for repository replication. We investigate how dissemination of repository contents can be ``piggybacked'' on top of existing email and Usenet traffic. Long-term persistence of the replicated repository may be achieved thanks to current policies and procedures which ensure that mail messages and news posts are retrievable for evidentiary and other legal purposes for many years after the creation date. While the preservation issues of migration and emulation are not addressed with this approach, it does provide a simple method of refreshing content with unknown partners.
Building a logical model in the machining domain for CAPP expert systems
Venue: arXiv cs.AI 2006
Year: 2006

Recently, extensive efforts have been made on the application of expert system technique to solving the process planning task in the machining domain. This paper introduces a new formal method to design CAPP expert systems. The formal method is applied to provide a contour of the CAPP expert system building technology. Theoretical aspects of the formalism are described and illustrated by an example of know-how analysis. Flexible facilities to utilize multiple knowledge types and multiple planning strategies within one system are provided by the technology.
Affine Transformations of Loop Nests for Parallel Execution and Distribution of Data over Processors
Venue: arXiv cs.DC 2006
Year: 2006

The paper is devoted to the problem of mapping affine loop nests onto distributed memory parallel computers. A method to find affine transformations of loop nests for parallel execution and distribution of data over processors is presented. The method tends to minimize the number of communications between processors and to improve locality of data within one processor. A problem of determination of data exchange sequence is investigated. Conditions to determine the ability to arrange broadcast is presented.