OpenRaiser/Intern-Atlas huggingface dataset:
Fuzzy Relational Modeling of Cost and Affordability for Advanced Technology Manufacturing Environment
Venue: arXiv cs.CE 2003
Year: 2003

Relational representation of knowledge makes it possible to perform all the computations and decision making in a uniform relational way by means of special relational compositions called triangle and square products. In this paper some applications in manufacturing related to cost analysis are described. Testing fuzzy relational structures for various relational properties allows us to discover dependencies, hierarchies, similarities, and equivalences of the attributes characterizing technological processes and manufactured artifacts in their relationship to costs and performance. A brief overview of mathematical aspects of BK-relational products is given in Appendix 1 together with further references in the literature.
Optimizing Noncontiguous Accesses in MPI-IO
Venue: arXiv cs.DC 2003
Year: 2003

The I/O access patterns of many parallel applications consist of accesses to a large number of small, noncontiguous pieces of data. If an application's I/O needs are met by making many small, distinct I/O requests, however, the I/O performance degrades drastically. To avoid this problem, MPI-IO allows users to access noncontiguous data with a single I/O function call, unlike in Unix I/O. In this paper, we explain how critical this feature of MPI-IO is for high performance and how it enables implementations to perform optimizations. We first provide a classification of the different ways of expressing an application's I/O needs in MPI-IO--we classify them into four levels, called level~0 through level~3. We demonstrate that, for applications with noncontiguous access patterns, the I/O performance improves dramatically if users write their applications to make level-3 requests (noncontiguous, collective) rather than level-0 requests (Unix style). We then describe how our MPI-IO implementation, ROMIO, delivers high performance for noncontiguous requests. We explain in detail the two key optimizations ROMIO performs: data sieving for noncontiguous requests from one process and collective I/O for noncontiguous requests from multiple processes. We describe how we have implemented these optimizations portably on multiple machines and file systems, controlled their memory requirements, and also achieved high performance. We demonstrate the performance and portability with performance results for three applications--an astrophysics-application template (DIST3D), the NAS BTIO benchmark, and an unstructured code (UNSTRUC)--on five different parallel machines: HP Exemplar, IBM SP, Intel Paragon, NEC SX-4, and SGI Origin2000.
A Game Theoretic Framework for Incentives in P2P Systems
Venue: arXiv cs.GT 2003
Year: 2003

Peer-To-Peer (P2P) networks are self-organizing, distributed systems, with no centralized authority or infrastructure. Because of the voluntary participation, the availability of resources in a P2P system can be highly variable and unpredictable. In this paper, we use ideas from Game Theory to study the interaction of strategic and rational peers, and propose a differential service-based incentive scheme to improve the system's performance.
Managing Evolving Business Workflows through the Capture of Descriptive Information
Venue: arXiv cs.SE 2003
Year: 2003

Business systems these days need to be agile to address the needs of a changing world. In particular the discipline of Enterprise Application Integration requires business process management to be highly reconfigurable with the ability to support dynamic workflows, inter-application integration and process reconfiguration. Basing EAI systems on model-resident or on a so-called description-driven approach enables aspects of flexibility, distribution, system evolution and integration to be addressed in a domain-independent manner. Such a system called CRISTAL is described in this paper with particular emphasis on its application to EAI problem domains. A practical example of the CRISTAL technology in the domain of manufacturing systems, called Agilium, is described to demonstrate the principles of model-driven system evolution and integration. The approach is compared to other model-driven development approaches such as the Model-Driven Architecture of the OMG and so-called Adaptive Object Models.
Satisfiability and computing van der Waerden numbers
Venue: arXiv cs.LO 2003
Year: 2003

In this paper we bring together the areas of combinatorics and propositional satisfiability. Many combinatorial theorems establish, often constructively, the existence of positive integer functions, without actually providing their closed algebraic form or tight lower and upper bounds. The area of Ramsey theory is especially rich in such results. Using the problem of computing van der Waerden numbers as an example, we show that these problems can be represented by parameterized propositional theories in such a way that decisions concerning their satisfiability determine the numbers (function) in question. We show that by using general-purpose complete and local-search techniques for testing propositional satisfiability, this approach becomes effective -- competitive with specialized approaches. By following it, we were able to obtain several new results pertaining to the problem of computing van der Waerden numbers. We also note that due to their properties, especially their structural simplicity and computational hardness, propositional theories that arise in this research can be of use in development, testing and benchmarking of SAT solvers.
A rigorous definition of axial lines: ridges on isovist fields
Venue: arXiv cs.CV 2003
Year: 2003

We suggest that 'axial lines' defined by (Hillier and Hanson, 1984) as lines of uninterrupted movement within urban streetscapes or buildings, appear as ridges in isovist fields (Benedikt, 1979). These are formed from the maximum diametric lengths of the individual isovists, sometimes called viewsheds, that make up these fields (Batty and Rana, 2004). We present an image processing technique for the identification of lines from ridges, discuss current strengths and weaknesses of the method, and show how it can be implemented easily and effectively.
Make search become the internal function of Internet
Venue: arXiv cs.IR 2003
Year: 2003

Domain Resource Integrated System (DRIS) is introduced in this paper. DRIS is a distributed information retrieval system, which will solve problems like poor coverage, long update interval in current web search system. The most distinct character of DRIS is that it's a public opening system, and acts as an internal component of Internet, but not the production of a company. The implementation of DRIS is also represented.
S-ToPSS: Semantic Toronto Publish/Subscribe System
Venue: arXiv cs.DC 2003
Year: 2003

The increase in the amount of data on the Internet has led to the development of a new generation of applications based on selective information dissemination where, data is distributed only to interested clients. Such applications require a new middleware architecture that can efficiently match user interests with available information. Middleware that can satisfy this requirement include event-based architectures such as publish-subscribe systems. In this demonstration paper we address the problem of semantic matching. We investigate how current publish/subscribe systems can be extended with semantic capabilities. Our main contribution is the development and validation (through demonstration) of a semantic pub/sub system prototype S-ToPSS (Semantic Toronto Publish/Subscribe System).
Toward Attribute Efficient Learning Algorithms
Venue: arXiv cs.LG 2003
Year: 2003

We make progress on two important problems regarding attribute efficient learnability. First, we give an algorithm for learning decision lists of length $k$ over $n$ variables using $2^{\tilde{O}(k^{1/3})} \log n$ examples and time $n^{\tilde{O}(k^{1/3})}$. This is the first algorithm for learning decision lists that has both subexponential sample complexity and subexponential running time in the relevant parameters. Our approach establishes a relationship between attribute efficient learning and polynomial threshold functions and is based on a new construction of low degree, low weight polynomial threshold functions for decision lists. For a wide range of parameters our construction matches a 1994 lower bound due to Beigel for the ODDMAXBIT predicate and gives an essentially optimal tradeoff between polynomial threshold function degree and weight. Second, we give an algorithm for learning an unknown parity function on $k$ out of $n$ variables using $O(n^{1-1/k})$ examples in time polynomial in $n$. For $k=o(\log n)$ this yields a polynomial time algorithm with sample complexity $o(n)$. This is the first polynomial time algorithm for learning parity on a superconstant number of variables with sublinear sample complexity.
Turning CARTwheels: An Alternating Algorithm for Mining Redescriptions
Venue: arXiv cs.CE 2003
Year: 2003

We present an unusual algorithm involving classification trees where two trees are grown in opposite directions so that they are matched at their leaves. This approach finds application in a new data mining task we formulate, called "redescription mining". A redescription is a shift-of-vocabulary, or a different way of communicating information about a given subset of data; the goal of redescription mining is to find subsets of data that afford multiple descriptions. We highlight the importance of this problem in domains such as bioinformatics, which exhibit an underlying richness and diversity of data descriptors (e.g., genes can be studied in a variety of ways). Our approach helps integrate multiple forms of characterizing datasets, situates the knowledge gained from one dataset in the context of others, and harnesses high-level abstractions for uncovering cryptic and subtle features of data. Algorithm design decisions, implementation details, and experimental results are presented.
Verification of recursive parallel systems
Venue: arXiv cs.LO 2003
Year: 2003

In this paper we consider the problem of proving properties of infinite behaviour of formalisms suitable to describe (infinite state) systems with recursion and parallelism. As a formal setting, we consider the framework of Process Rewriting Systems (PRSs). For a meaningfull fragment of PRSs, allowing to accommodate both Pushdown Automata and Petri Nets, we state decidability results for a class of properties about infinite derivations (infinite term rewritings). The given results can be exploited for the automatic verification of some classes of linear time properties of infinite state systems described by PRSs. In order to exemplify the assessed results, we introduce a meaningful automaton based formalism which allows to express both recursion and multi--treading.
Soft Constraint Programming to Analysing Security Protocols
Venue: arXiv cs.CR 2003
Year: 2003

Security protocols stipulate how the remote principals of a computer network should interact in order to obtain specific security goals. The crucial goals of confidentiality and authentication may be achieved in various forms, each of different strength. Using soft (rather than crisp) constraints, we develop a uniform formal notion for the two goals. They are no longer formalised as mere yes/no properties as in the existing literature, but gain an extra parameter, the security level. For example, different messages can enjoy different levels of confidentiality, or a principal can achieve different levels of authentication with different principals. The goals are formalised within a general framework for protocol analysis that is amenable to mechanisation by model checking. Following the application of the framework to analysing the asymmetric Needham-Schroeder protocol, we have recently discovered a new attack on that protocol as a form of retaliation by principals who have been attacked previously. Having commented on that attack, we then demonstrate the framework on a bigger, largely deployed protocol consisting of three phases, Kerberos.
An Open Ended Tree
Venue: arXiv cs.PL 2003
Year: 2003

An open ended list is a well known data structure in Prolog programs. It is frequently used to represent a value changing over time, while this value is referred to from several places in the data structure of the application. A weak point in this technique is that the time complexity is linear in the number of updates to the value represented by the open ended list. In this programming pearl we present a variant of the open ended list, namely an open ended tree, with an update and access time complexity logarithmic in the number of updates to the value.
Towards Automated Generation of Scripted Dialogue: Some Time-Honoured Strategies
Venue: arXiv cs.CL 2003
Year: 2003

The main aim of this paper is to introduce automated generation of scripted dialogue as a worthwhile topic of investigation. In particular the fact that scripted dialogue involves two layers of communication, i.e., uni-directional communication between the author and the audience of a scripted dialogue and bi-directional pretended communication between the characters featuring in the dialogue, is argued to raise some interesting issues. Our hope is that the combined study of the two layers will forge links between research in text generation and dialogue processing. The paper presents a first attempt at creating such links by studying three types of strategies for the automated generation of scripted dialogue. The strategies are derived from examples of human-authored and naturally occurring dialogue.
Nondeterministic Quantum Query and Quantum Communication Complexities
Venue: arXiv cs.CC 2004
Year: 2004

We study nondeterministic quantum algorithms for Boolean functions f. Such algorithms have positive acceptance probability on input x iff f(x)=1. In the setting of query complexity, we show that the nondeterministic quantum complexity of a Boolean function is equal to its ``nondeterministic polynomial'' degree. We also prove a quantum-vs-classical gap of 1 vs n for nondeterministic query complexity for a total function. In the setting of communication complexity, we show that the nondeterministic quantum complexity of a two-party function is equal to the logarithm of the rank of a nondeterministic version of the communication matrix. This implies that the quantum communication complexities of the equality and disjointness functions are n+1 if we do not allow any error probability. We also exhibit a total function in which the nondeterministic quantum communication complexity is exponentially smaller than its classical counterpart.
Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem
Venue: arXiv cs.CC 2004
Year: 2004

We prove that the exact versions of the domatic number problem are complete for the levels of the boolean hierarchy over NP. The domatic number problem, which arises in the area of computer networks, is the problem of partitioning a given graph into a maximum number of disjoint dominating sets. This number is called the domatic number of the graph. We prove that the problem of determining whether or not the domatic number of a given graph is {\em exactly} one of k given values is complete for the 2k-th level of the boolean hierarchy over NP. In particular, for k = 1, it is DP-complete to determine whether or not the domatic number of a given graph equals exactly a given integer. Note that DP is the second level of the boolean hierarchy over NP. We obtain similar results for the exact versions of generalized dominating set problems and of the conveyor flow shop problem. Our reductions apply Wagner's conditions sufficient to prove hardness for the levels of the boolean hierarchy over NP.
The Complexity of Boolean Constraint Isomorphism
Venue: arXiv cs.CC 2004
Year: 2004

In 1978, Schaefer proved his famous dichotomy theorem for generalized satisfiability problems. He defined an infinite number of propositional satisfiability problems (nowadays usually called Boolean constraint satisfaction problems) and showed that all these satisfiability problems are either in P or NP-complete. In recent years, similar results have been obtained for quite a few other problems for Boolean constraints.Almost all of these problems are variations of the satisfiability problem. In this paper, we address a problem that is not a variation of satisfiability, namely, the isomorphism problem for Boolean constraints. Previous work by Böhler et al. showed that the isomorphism problem is either coNP-hard or reducible to the graph isomorphism problem (a problem that is in NP, but not known to be NP-hard), thus distinguishing a hard case and an easier case. However, they did not classify which cases are truly easy, i.e., in P. This paper accomplishes exactly that. It shows that Boolean constraint isomorphism is coNP-hard (and GI-hard), or equivalent to graph isomorphism, or in P, and it gives simple criteria to determine which case holds.
Neural realisation of the SP theory: cell assemblies revisited
Venue: arXiv cs.AI 2004
Year: 2004

This paper describes how the elements of the SP theory (Wolff, 2003a) may be realised with neural structures and processes. To the extent that this is successful, the insights that have been achieved in the SP theory - the integration and simplification of a range of phenomena in perception and cognition - may be incorporated in a neural view of brain function. These proposals may be seen as a development of Hebb's (1949) concept of a 'cell assembly'. By contrast with that concept and variants of it, the version described in this paper proposes that any one neuron can belong in one assembly and only one assembly. A distinctive feature of the present proposals is that any neuron or cluster of neurons within a cell assembly may serve as a proxy or reference for another cell assembly or class of cell assemblies. This device provides solutions to many of the problems associated with cell assemblies, it allows information to be stored in a compressed form, and it provides a robust mechanism by which assemblies may be connected to form hierarchies, grammars and other kinds of knowledge structure. Drawing on insights derived from the SP theory, the paper also describes how unsupervised learning may be achieved with neural structures and processes. This theory of learning overcomes weaknesses in the Hebbian concept of learning and it is, at the same time, compatible with the observations that Hebb's theory was designed to explain.
Cyborg Systems as Platforms for Computer-Vision Algorithm-Development for Astrobiology
Venue: arXiv cs.CV 2004
Year: 2004

Employing the allegorical imagery from the film "The Matrix", we motivate and discuss our `Cyborg Astrobiologist' research program. In this research program, we are using a wearable computer and video camcorder in order to test and train a computer-vision system to be a field-geologist and field-astrobiologist.
Cluster computing performances using virtual processors and mathematical software
Venue: arXiv cs.DC 2004
Year: 2004

In this paper I describe some results on the use of virtual processors technology for parallelize some SPMD computational programs in a cluster environment. The tested technology is the INTEL Hyper Threading on real processors, and the programs are MATLAB 6.5 Release 13 scripts for floating points computation. By the use of this technology, I tested that a cluster can run with benefit a number of concurrent processes double the amount of physical processors. The conclusions of the work concern on the utility and limits of the used approach. The main result is that using virtual processors is a good technique for improving parallel programs not only for memory-based computations, but in the case of massive disk-storage operations too.
Algebraic Elimination of epsilon-transitions
Venue: arXiv cs.SC 2004
Year: 2004

We present here algebraic formulas associating a k-automaton to a k-epsilon-automaton. The existence depends on the definition of the star of matrices and of elements in the semiring k. For this reason, we present the theorem which allows the transformation of k-epsilon-automata into k-automata. The two automata have the same behaviour.
Factor Temporal Prognosis of Tick-Borne Encephalitis Foci Functioning on the South of Russian Far East
Venue: arXiv cs.CV 2004
Year: 2004

A method of temporal factor prognosis of TE (tick-borne encephalitis) infection has been developed. The high precision of the prognosis results for a number of geographical regions of Primorsky Krai has been achieved. The method can be applied not only to epidemiological research but also to others.
Pseudorandom number generation by $p$-adic ergodic transformations
Venue: arXiv cs.CR 2004
Year: 2004

The paper study counter-dependent pseudorandom generators; the latter are generators such that their state transition function (and output function) is being modified dynamically while working: For such a generator the recurrence sequence of states satisfies a congruence $x_{i+1}\equiv f_i(x_i)\pmod{2^n}$, while its output sequence is of the form $z_{i}=F_i(u_i)$. The paper introduces techniques and constructions that enable one to compose generators that output uniformly distributed sequences of a maximum period length and with high linear and 2-adic spans. The corresponding stream chipher is provably strong against a known plaintext attack (up to a plausible conjecture). Both state transition function and output function could be key-dependent, so the only information available to a cryptanalyst is that these functions belong to some (exponentially large) class. These functions are compositions of standard machine instructions (such as addition, multiplication, bitwise logical operations, etc.) The compositions should satisfy rather loose conditions; so the corresponding generators are flexible enough and could be easily implemented as computer programs.
Accurately modeling the Internet topology
Venue: arXiv cs.NI 2004
Year: 2004

Based on measurements of the Internet topology data, we found out that there are two mechanisms which are necessary for the correct modeling of the Internet topology at the Autonomous Systems (AS) level: the Interactive Growth of new nodes and new internal links, and a nonlinear preferential attachment, where the preference probability is described by a positive-feedback mechanism. Based on the above mechanisms, we introduce the Positive-Feedback Preference (PFP) model which accurately reproduces many topological properties of the AS-level Internet, including: degree distribution, rich-club connectivity, the maximum degree, shortest path length, short cycles, disassortative mixing and betweenness centrality. The PFP model is a phenomenological model which provides a novel insight into the evolutionary dynamics of real complex networks.
Self-Organising Networks for Classification: developing Applications to Science Analysis for Astroparticle Physics
Venue: arXiv cs.NE 2004
Year: 2004

Physics analysis in astroparticle experiments requires the capability of recognizing new phenomena; in order to establish what is new, it is important to develop tools for automatic classification, able to compare the final result with data from different detectors. A typical example is the problem of Gamma Ray Burst detection, classification, and possible association to known sources: for this task physicists will need in the next years tools to associate data from optical databases, from satellite experiments (EGRET, GLAST), and from Cherenkov telescopes (MAGIC, HESS, CANGAROO, VERITAS).