OpenRaiser/Intern-Atlas huggingface dataset:
The role of robust semantic analysis in spoken language dialogue systems
Venue: arXiv cs.CL 2004
Year: 2004

In this paper we summarized a framework for designing grammar-based procedure for the automatic extraction of the semantic content from spoken queries. Starting with a case study and following an approach which combines the notions of fuzziness and robustness in sentence parsing, we showed we built practical domain-dependent rules which can be applied whenever it is possible to superimpose a sentence-level semantic structure to a text without relying on a previous deep syntactical analysis. This kind of procedure can be also profitably used as a pre-processing tool in order to cut out part of the sentence which have been recognized to have no relevance in the understanding process. In the case of particular dialogue applications where there is no need to build a complex semantic structure (e.g. word spotting or excerpting) the presented methodology may represent an efficient alternative solution to a sequential composition of deep linguistic analysis modules. Even if the query generation problem may not seem a critical application it should be held in mind that the sentence processing must be done on-line. Having this kind of constraints we cannot design our system without caring for efficiency and thus provide an immediate response. Another critical issue is related to whole robustness of the system. In our case study we tried to make experiences on how it is possible to deal with an unreliable and noisy input without asking the user for any repetition or clarification. This may correspond to a similar problem one may have when processing text coming from informal writing such as e-mails, news and in many cases Web pages where it is often the case to have irrelevant surrounding information.
Verbal chunk extraction in French using limited resources
Venue: arXiv cs.CL 2004
Year: 2004

A way of extracting French verbal chunks, inflected and infinitive, is explored and tested on effective corpus. Declarative morphological and local grammar rules specifying chunks and some simple contextual structures are used, relying on limited lexical information and some simple heuristic/statistic properties obtained from restricted corpora. The specific goals, the architecture and the formalism of the system, the linguistic information on which it relies and the obtained results on effective corpus are presented.
The Core of Directed Network Problems with Quotas
Venue: arXiv cs.GT 2004
Year: 2004

This paper proves the existence of non-empty cores for directed network problems with quotas and for those combinatorial allocation problems which permit only exclusive allocations.
Robust Locally Testable Codes and Products of Codes
Venue: arXiv cs.IT 2004
Year: 2004

We continue the investigation of locally testable codes, i.e., error-correcting codes for whom membership of a given word in the code can be tested probabilistically by examining it in very few locations. We give two general results on local testability: First, motivated by the recently proposed notion of {\em robust} probabilistically checkable proofs, we introduce the notion of {\em robust} local testability of codes. We relate this notion to a product of codes introduced by Tanner, and show a very simple composition lemma for this notion. Next, we show that codes built by tensor products can be tested robustly and somewhat locally, by applying a variant of a test and proof technique introduced by Raz and Safra in the context of testing low-degree multivariate polynomials (which are a special case of tensor codes). Combining these two results gives us a generic construction of codes of inverse polynomial rate, that are testable with poly-logarithmically many queries. We note these locally testable tensor codes can be obtained from {\em any} linear error correcting code with good distance. Previous results on local testability, albeit much stronger quantitatively, rely heavily on algebraic properties of the underlying codes.
Locally connected spanning trees on graphs
Venue: arXiv cs.DS 2004
Year: 2004

A locally connected spanning tree of a graph $G$ is a spanning tree $T$ of $G$ such that the set of all neighbors of $v$ in $T$ induces a connected subgraph of $G$ for every $v\in V(G)$. The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.
Capacity-achieving ensembles for the binary erasure channel with bounded complexity
Venue: arXiv cs.IT 2004
Year: 2004

We present two sequences of ensembles of non-systematic irregular repeat-accumulate codes which asymptotically (as their block length tends to infinity) achieve capacity on the binary erasure channel (BEC) with bounded complexity per information bit. This is in contrast to all previous constructions of capacity-achieving sequences of ensembles whose complexity grows at least like the log of the inverse of the gap (in rate) to capacity. The new bounded complexity result is achieved by puncturing bits, and allowing in this way a sufficient number of state nodes in the Tanner graph representing the codes. We also derive an information-theoretic lower bound on the decoding complexity of randomly punctured codes on graphs. The bound holds for every memoryless binary-input output-symmetric channel and is refined for the BEC.
Securing Data in Storage: A Review of Current Research
Venue: arXiv cs.OS 2004
Year: 2004

Protecting data from malicious computer users continues to grow in importance. Whether preventing unauthorized access to personal photographs, ensuring compliance with federal regulations, or ensuring the integrity of corporate secrets, all applications require increased security to protect data from talented intruders. Specifically, as more and more files are preserved on disk the requirement to provide secure storage has increased in importance. This paper presents a survey of techniques for securely storing data, including theoretical approaches, prototype systems, and existing systems currently available. Due to the wide variety of potential solutions available and the variety of techniques to arrive at a particular solution, it is important to review the entire field prior to selecting an implementation that satisfies particular requirements. This paper provides an overview of the prominent characteristics of several systems to provide a foundation for making an informed decision. Initially, the paper establishes a set of criteria for evaluating a storage solution based on confidentiality, integrity, availability, and performance. Then, using these criteria, the paper explains the relevant characteristics of select storage systems and provides a comparison of the major differences.
Unification of Fusion Theories
Venue: arXiv cs.AI 2004
Year: 2004

Since no fusion theory neither rule fully satisfy all needed applications, the author proposes a Unification of Fusion Theories and a combination of fusion rules in solving problems/applications. For each particular application, one selects the most appropriate model, rule(s), and algorithm of implementation. We are working in the unification of the fusion theories and rules, which looks like a cooking recipe, better we'd say like a logical chart for a computer programmer, but we don't see another method to comprise/unify all things. The unification scenario presented herein, which is now in an incipient form, should periodically be updated incorporating new discoveries from the fusion and engineering research.
Some Applications of Coding Theory in Computational Complexity
Venue: arXiv cs.CC 2004
Year: 2004

Error-correcting codes and related combinatorial constructs play an important role in several recent (and old) results in computational complexity theory. In this paper we survey results on locally-testable and locally-decodable error-correcting codes, and their applications to complexity theory and to cryptography. Locally decodable codes are error-correcting codes with sub-linear time error-correcting algorithms. They are related to private information retrieval (a type of cryptographic protocol), and they are used in average-case complexity and to construct ``hard-core predicates'' for one-way permutations. Locally testable codes are error-correcting codes with sub-linear time error-detection algorithms, and they are the combinatorial core of probabilistically checkable proofs.
On the role of MMSE estimation in approaching the information-theoretic limits of linear Gaussian channels: Shannon meets Wiener
Venue: arXiv cs.IT 2004
Year: 2004

We discuss why MMSE estimation arises in lattice-based schemes for approaching the capacity of linear Gaussian channels, and comment on its properties.
An Approximation Algorithm for Stackelberg Network Pricing
Venue: arXiv cs.GT 2004
Year: 2004

We consider the problem of maximizing the revenue raised from tolls set on the arcs of a transportation network, under the constraint that users are assigned to toll-compatible shortest paths. We first prove that this problem is strongly NP-hard. We then provide a polynomial time algorithm with a worst-case precision guarantee of ${1/2}\log_2 m_T+1$, where $m_T$ denotes the number of toll arcs. Finally we show that the approximation is tight with respect to a natural relaxation by constructing a family of instances for which the relaxation gap is reached.
Applying Policy Iteration for Training Recurrent Neural Networks
Venue: arXiv cs.AI 2004
Year: 2004

Recurrent neural networks are often used for learning time-series data. Based on a few assumptions we model this learning task as a minimization problem of a nonlinear least-squares cost function. The special structure of the cost function allows us to build a connection to reinforcement learning. We exploit this connection and derive a convergent, policy iteration-based algorithm. Furthermore, we argue that RNN training can be fit naturally into the reinforcement learning framework.
A dynamical model of a GRID market
Venue: arXiv cs.MA 2004
Year: 2004

We discuss potential market mechanisms for the GRID. A complete dynamical model of a GRID market is defined with three types of agents. Providers, middlemen and users exchange universal GRID computing units (GCUs) at varying prices. Providers and middlemen have strategies aimed at maximizing profit while users are 'satisficing' agents, and only change their behavior if the service they receive is sufficiently poor or overpriced. Preliminary results from a multi-agent numerical simulation of the market model shows that the distribution of price changes has a power law tail.
Demo or Practice: Critical Analysis of the Language/Action Perspective
Venue: arXiv cs.OH 2004
Year: 2004

Despite offering several promising concepts, the Language/Action Perspective (LAP) is still not in the mainstream of Information Systems Development (ISD). Since at present there is only a limited understanding of LAP theory and practice, it remains unclear whether the lack of LAP's impact is due to shortcomings in LAP theory itself. One classic problem within ISD is the dichotomy between social perspectives and technical perspectives. LAP claims it offers a solution to this problem. This paper investigates this claim as a means to review LAP theory. To provide a structure to a critical analysis of DEMO - an example methodology that belongs to the LAP research community - this paper utilizes a paradigmatic framework. This framework is augmented by the opinion of several DEMO practitioners by means of an expert discussion. With use of a comparative evaluation of LAP theory and DEMO theory, the implication of DEMO's reflection upon LAP is determined. The paper concludes by outlining an agenda for further research if LAP is to improve its footprint in the field.
A New Proxy Ring Signature Scheme
Venue: arXiv cs.CR 2004
Year: 2004

The concept of ring signature was introduced by Rivest, Shamir and Tauman. This signature is considered to be a simplified group signature from which identity of signer is ambiguous although verifier knows the group to which signer belong. In this paper we introduce a new proxy ring signature scheme.
DiPerF: an automated DIstributed PERformance testing Framework
Venue: arXiv cs.PF 2004
Year: 2004

We present DiPerF, a distributed performance testing framework, aimed at simplifying and automating service performance evaluation. DiPerF coordinates a pool of machines that test a target service, collects and aggregates performance metrics, and generates performance statistics. The aggregate data collected provide information on service throughput, on service "fairness" when serving multiple clients concurrently, and on the impact of network latency on service performance. Furthermore, using this data, it is possible to build predictive models that estimate a service performance given the service load. We have tested DiPerF on 100+ machines on two testbeds, Grid3 and PlanetLab, and explored the performance of job submission services (pre WS GRAM and WS GRAM) included with Globus Toolkit 3.2.
Automated Pattern Detection--An Algorithm for Constructing Optimally Synchronizing Multi-Regular Language Filters
Venue: arXiv cs.CV 2004
Year: 2004

In the computational-mechanics structural analysis of one-dimensional cellular automata the following automata-theoretic analogue of the \emph{change-point problem} from time series analysis arises: \emph{Given a string $σ$ and a collection $\{\mc{D}_i\}$ of finite automata, identify the regions of $σ$ that belong to each $\mc{D}_i$ and, in particular, the boundaries separating them.} We present two methods for solving this \emph{multi-regular language filtering problem}. The first, although providing the ideal solution, requires a stack, has a worst-case compute time that grows quadratically in $σ$'s length and conditions its output at any point on arbitrarily long windows of future input. The second method is to algorithmically construct a transducer that approximates the first algorithm. In contrast to the stack-based algorithm, however, the transducer requires only a finite amount of memory, runs in linear time, and gives immediate output for each letter read; it is, moreover, the best possible finite-state approximation with these three features.
Adaptive Cluster Expansion (ACE): A Hierarchical Bayesian Network
Venue: arXiv cs.NE 2004
Year: 2004

Using the maximum entropy method, we derive the "adaptive cluster expansion" (ACE), which can be trained to estimate probability density functions in high dimensional spaces. The main advantage of ACE over other Bayesian networks is its ability to capture high order statistics after short training times, which it achieves by making use of a hierarchical vector quantisation of the input data. We derive a scheme for representing the state of an ACE network as a "probability image", which allows us to identify statistically anomalous regions in an otherwise statistically homogeneous image, for instance. Finally, we present some probability images that we obtained after training ACE on some Brodatz texture images - these demonstrate the ability of ACE to detect subtle textural anomalies.
Complexity Results in Graph Reconstruction
Venue: arXiv cs.CC 2004
Year: 2004

We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts $c \geq 1$ of deletion: 1) $GI \equiv^{l}_{iso} VDC_{c}$, $GI \equiv^{l}_{iso} EDC_{c}$, $GI \leq^{l}_{m} LVD_c$, and $GI \equiv^{p}_{iso} LED_c$. 2) For all $k \geq 2$, $GI \equiv^{p}_{iso} k-VDC_c$ and $GI \equiv^{p}_{iso} k-EDC_c$. 3) For all $k \geq 2$, $GI \leq^{l}_{m} k-LVD_c$. 4)$GI \equiv^{p}_{iso} 2-LVC_c$. 5) For all $k \geq 2$, $GI \equiv^{p}_{iso} k-LED_c$. For many of these results, even the $c = 1$ case was not previously known. Similar to the definition of reconstruction numbers $vrn_{\exists}(G)$ [HP85] and $ern_{\exists}(G)$ (see page 120 of [LS03]), we introduce two new graph parameters, $vrn_{\forall}(G)$ and $ern_{\forall}(G)$, and give an example of a family $\{G_n\}_{n \geq 4}$ of graphs on $n$ vertices for which $vrn_{\exists}(G_n) < vrn_{\forall}(G_n)$. For every $k \geq 2$ and $n \geq 1$, we show that there exists a collection of $k$ graphs on $(2^{k-1}+1)n+k$ vertices with $2^{n}$ 1-vertex-preimages, i.e., one has families of graph collections whose number of 1-vertex-preimages is huge relative to the size of the graphs involved.
RRL: A Rich Representation Language for the Description of Agent Behaviour in NECA
Venue: arXiv cs.MM 2004
Year: 2004

In this paper, we describe the Rich Representation Language (RRL) which is used in the NECA system. The NECA system generates interactions between two or more animated characters. The RRL is an XML compliant framework for representing the information that is exchanged at the interfaces between the various NECA system modules. The full XML Schemas for the RRL are available at http://www.ai.univie.ac.at/NECA/RRL
Lattice QCD Data and Metadata Archives at Fermilab and the International Lattice Data Grid
Venue: arXiv cs.DC 2004
Year: 2004

The lattice gauge theory community produces large volumes of data. Because the data produced by completed computations form the basis for future work, the maintenance of archives of existing data and metadata describing the provenance, generation parameters, and derived characteristics of that data is essential not only as a reference, but also as a basis for future work. Development of these archives according to uniform standards both in the data and metadata formats provided and in the software interfaces to the component services could greatly simplify collaborations between institutions and enable the dissemination of meaningful results. This paper describes the progress made in the development of a set of such archives at the Fermilab lattice QCD facility. We are coordinating the development of the interfaces to these facilities and the formats of the data and metadata they provide with the efforts of the international lattice data grid (ILDG) metadata and middleware working groups, whose goals are to develop standard formats for lattice QCD data and metadata and a uniform interface to archive facilities that store them. Services under development include those commonly associate with data grids: a service registry, a metadata database, a replica catalog, and an interface to a mass storage system. All services provide GSI authenticated web service interfaces following modern standards, including WSDL and SOAP, and accept and provide data and metadata following recent XML based formats proposed by the ILDG metadata working group.
Life Above Threshold: From List Decoding to Area Theorem and MSE
Venue: arXiv cs.IT 2004
Year: 2004

We consider communication over memoryless channels using low-density parity-check code ensembles above the iterative (belief propagation) threshold. What is the computational complexity of decoding (i.e., of reconstructing all the typical input codewords for a given channel output) in this regime? We define an algorithm accomplishing this task and analyze its typical performance. The behavior of the new algorithm can be expressed in purely information-theoretical terms. Its analysis provides an alternative proof of the area theorem for the binary erasure channel. Finally, we explain how the area theorem is generalized to arbitrary memoryless channels. We note that the recently discovered relation between mutual information and minimal square error is an instance of the area theorem in the setting of Gaussian channels.
Intransitivity and Vagueness
Venue: arXiv cs.AI 2004
Year: 2004

There are many examples in the literature that suggest that indistinguishability is intransitive, despite the fact that the indistinguishability relation is typically taken to be an equivalence relation (and thus transitive). It is shown that if the uncertainty perception and the question of when an agent reports that two things are indistinguishable are both carefully modeled, the problems disappear, and indistinguishability can indeed be taken to be an equivalence relation. Moreover, this model also suggests a logic of vagueness that seems to solve many of the problems related to vagueness discussed in the philosophical literature. In particular, it is shown here how the logic can handle the sorites paradox.
Intelligent Computer Numerical Control unit for machine tools
Venue: arXiv cs.CE 2004
Year: 2004

The paper describes a new CNC control unit for machining centres with learning ability and automatic intelligent generating of NC programs on the bases of a neural network, which is built-in into a CNC unit as special device. The device performs intelligent and completely automatically the NC part programs only on the bases of 2D, 2,5D or 3D computer model of prismatic part. Intervention of the operator is not needed. The neural network for milling, drilling, reaming, threading and operations alike has learned to generate NC programs in the learning module, which is a part of intelligent CAD/CAM system.
ReCord: A Distributed Hash Table with Recursive Structure
Venue: arXiv cs.DC 2004
Year: 2004

We propose a simple distributed hash table called ReCord, which is a generalized version of Randomized-Chord and offers improved tradeoffs in performance and topology maintenance over existing P2P systems. ReCord is scalable and can be easily implemented as an overlay network, and offers a good tradeoff between the node degree and query latency. For instance, an $n$-node ReCord with $O(\log n)$ node degree has an expected latency of $Θ(\log n)$ hops. Alternatively, it can also offer $Θ(\frac{\log n}{\log \log n})$ hops latency at a higher cost of $O(\frac{\log^2 n}{\log \log n})$ node degree. Meanwhile, simulations of the dynamic behaviors of ReCord are studied.
Capacity Achieving Code Constructions for Two Classes of (d,k) Constraints
Venue: arXiv cs.IT 2004
Year: 2004

In this paper, we present two low complexity algorithms that achieve capacity for the noiseless (d,k) constrained channel when k=2d+1, or when k-d+1 is not prime. The first algorithm, called symbol sliding, is a generalized version of the bit flipping algorithm introduced by Aviran et al. [1]. In addition to achieving capacity for (d,2d+1) constraints, it comes close to capacity in other cases. The second algorithm is based on interleaving, and is a generalized version of the bit stuffing algorithm introduced by Bender and Wolf [2]. This method uses fewer than k-d biased bit streams to achieve capacity for (d,k) constraints with k-d+1 not prime. In particular, the encoder for (d,d+2^m-1) constraints, 1\le m<\infty, requires only m biased bit streams.
A Trace Logic for Local Security Properties
Venue: arXiv cs.CR 2004
Year: 2004

We propose a new simple \emph{trace} logic that can be used to specify \emph{local security properties}, i.e. security properties that refer to a single participant of the protocol specification. Our technique allows a protocol designer to provide a formal specification of the desired security properties, and integrate it naturally into the design process of cryptographic protocols. Furthermore, the logic can be used for formal verification. We illustrate the utility of our technique by exposing new attacks on the well studied protocol TMN.