title: Proportional Conflict Redistribution Rules for Information Fusion

abstract: In this paper we propose five versions of a Proportional Conflict Redistribution rule (PCR) for information fusion together with several examples. From PCR1 to PCR2, PCR3, PCR4, PCR5 one increases the complexity of the rules and also the exactitude of the redistribution of conflicting masses. PCR1 restricted from the hyper-power set to the power set and without degenerate cases gives the same result as the Weighted Average Operator (WAO) proposed recently by J{\o}sang, Daniel and Vannoorenberghe but does not satisfy the neutrality property of vacuous belief assignment. That's why improved PCR rules are proposed in this paper. PCR4 is an improvement of minC and Dempster's rules. The PCR rules redistribute the conflicting mass, after the conjunctive rule has been applied, proportionally with some functions depending on the masses assigned to their corresponding columns in the mass matrix. There are infinitely many ways these functions (weighting factors) can be chosen depending on the complexity one wants to deal with in specific applications and fusion systems. Any fusion combination rule is at some degree ad-hoc.


title: The Core of Directed Network Problems with Quotas

abstract: 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.


title: Robust Locally Testable Codes and Products of Codes

abstract: 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.


title: The Expected Size of the Rule k Dominating Set

abstract: Rule k is a localized approximation algorithm that finds a small connected dominating set in a graph. We estimate the expected size of the Rule k dominating set for the model of random unit disk graphs constructed from n random points in an s_n by s_n square region of the plane.


title: Probabilistic Analysis of Rule 2

abstract: Li and Wu proposed Rule 2, a localized approximation algorithm that attempts to find a small connected dominating set in a graph. Here we study the asymptotic performance of Rule 2 on random unit disk graphs formed from n random points in an s_n by s_n square region of the plane. If s_n is below the threshold for connectivity, then Rule 2 produces a dominating set whose expected size is O(n/(loglog n)^{3/2}). We conjecture that this bound is not optimal.


title: The Integration of Connectionism and First-Order Knowledge Representation and Reasoning as a Challenge for Artificial Intelligence

abstract: Intelligent systems based on first-order logic on the one hand, and on artificial neural networks (also called connectionist systems) on the other, differ substantially. It would be very desirable to combine the robust neural networking machinery with symbolic knowledge representation and reasoning paradigms like logic programming in such a way that the strengths of either paradigm will be retained. Current state-of-the-art research, however, fails by far to achieve this ultimate goal. As one of the main obstacles to be overcome we perceive the question how symbolic knowledge can be encoded by means of connectionist systems: Satisfactory answers to this will naturally lead the way to knowledge extraction algorithms and to integrated neural-symbolic systems.


title: Probabilistic heuristics for disseminating information in networks

abstract: We study the problem of disseminating a piece of information through all the nodes of a network, given that it is known originally only to a single node. In the absence of any structural knowledge on the network other than the nodes' neighborhoods, this problem is traditionally solved by flooding all the network's edges. We analyze a recently introduced probabilistic algorithm for flooding and give an alternative probabilistic heuristic that can lead to some cost-effective improvements, like better trade-offs between the message and time complexities involved. We analyze the two algorithms both mathematically and by means of simulations, always within a random-graph framework and considering relevant node-degree distributions.


title: Default reasoning over domains and concept hierarchies

abstract: W.C. Rounds and G.-Q. Zhang (2001) have proposed to study a form of disjunctive logic programming generalized to algebraic domains. This system allows reasoning with information which is hierarchically structured and forms a (suitable) domain. We extend this framework to include reasoning with default negation, giving rise to a new nonmonotonic reasoning framework on hierarchical knowledge which encompasses answer set programming with extended disjunctive logic programs. We also show that the hierarchically structured knowledge on which programming in this paradigm can be done, arises very naturally from formal concept analysis. Together, we obtain a default reasoning paradigm for conceptual knowledge which is in accordance with mainstream developments in nonmonotonic reasoning.


title: ScheduleNanny: Using GPS to Learn the User's Significant Locations, Travel Times and Schedule

abstract: As computing technology becomes more pervasive, personal devices such as the PDA, cell-phone, and notebook should use context to determine how to act. Location is one form of context that can be used in many ways. We present a multiple-device system that collects and clusters GPS data into significant locations. These locations are then used to determine travel times and a probabilistic model of the user's schedule, which is used to intelligently alert the user. We evaluate our system and suggest how it should be integrated with a variety of applications.


title: The Password Change Phase is Still Insecure

abstract: In 2004, W. C. Ku and S. M. Chen proposed an efficient remote user authentication scheme using smart cards to solve the security problems of Chien et al.'s scheme. Recently, Hsu and Yoon et al. pointed out the security weaknesses of the Ku and Chen's scheme Furthermore, Yoon et al. also proposed a new efficient remote user authentication scheme using smart cards. Yoon et al. also modified the password change phase of Ku and Chen's scheme. This paper analyzes that password change phase of Yoon et al's modified scheme is still insecure.


title: Sharing Computer Network Logs for Security and Privacy: A Motivation for New Methodologies of Anonymization

abstract: Logs are one of the most fundamental resources to any security professional. It is widely recognized by the government and industry that it is both beneficial and desirable to share logs for the purpose of security research. However, the sharing is not happening or not to the degree or magnitude that is desired. Organizations are reluctant to share logs because of the risk of exposing sensitive information to potential attackers. We believe this reluctance remains high because current anonymization techniques are weak and one-size-fits-all--or better put, one size tries to fit all. We must develop standards and make anonymization available at varying levels, striking a balance between privacy and utility. Organizations have different needs and trust other organizations to different degrees. They must be able to map multiple anonymization levels with defined risks to the trust levels they share with (would-be) receivers. It is not until there are industry standards for multiple levels of anonymization that we will be able to move forward and achieve the goal of widespread sharing of logs for security researchers.


title: Maple+GrTensorII libraries for cosmology

abstract: The article mainly presents some results in using MAPLE platform for computer algebra and GrTensorII package in doing calculations for theoretical and numerical cosmology


title: The Generalized Pignistic Transformation

abstract: This paper presents in detail the generalized pignistic transformation (GPT) succinctly developed in the Dezert-Smarandache Theory (DSmT) framework as a tool for decision process. The GPT allows to provide a subjective probability measure from any generalized basic belief assignment given by any corpus of evidence. We mainly focus our presentation on the 3D case and provide the complete result obtained by the GPT and its validation drawn from the probability theory.


title: A Model for Fine-Grained Alignment of Multilingual Texts

abstract: While alignment of texts on the sentential level is often seen as being too coarse, and word alignment as being too fine-grained, bi- or multilingual texts which are aligned on a level in-between are a useful resource for many purposes. Starting from a number of examples of non-literal translations, which tend to make alignment difficult, we describe an alignment model which copes with these cases by explicitly coding them. The model is based on predicate-argument structures and thus covers the middle ground between sentence and word alignment. The model is currently used in a recently initiated project of a parallel English-German treebank (FuSe), which can in principle be extended with additional languages.


title: CrocoPat 2.1 Introduction and Reference Manual

abstract: CrocoPat is an efficient, powerful and easy-to-use tool for manipulating relations of arbitrary arity, including directed graphs. This manual provides an introduction to and a reference for CrocoPat and its programming language RML. It includes several application examples, in particular from the analysis of structural models of software systems.


title: Distance properties of expander codes

abstract: We study the minimum distance of codes defined on bipartite graphs. Weight spectrum and the minimum distance of a random ensemble of such codes are computed. It is shown that if the vertex codes have minimum distance $\ge 3$, the overall code is asymptotically good, and sometimes meets the Gilbert-Varshamov bound. Constructive families of expander codes are presented whose minimum distance asymptotically exceeds the product bound for all code rates between 0 and 1.


title: Shannon meets Wiener II: On MMSE estimation in successive decoding schemes

abstract: We continue to discuss why MMSE estimation arises in coding schemes that approach the capacity of linear Gaussian channels. Here we consider schemes that involve successive decoding, such as decision-feedback equalization or successive cancellation.


title: A New Look at Survey Propagation and its Generalizations

abstract: This paper provides a new conceptual perspective on survey propagation, which is an iterative algorithm recently introduced by the statistical physics community that is very effective in solving random k-SAT problems even with densities close to the satisfiability threshold. We first describe how any SAT formula can be associated with a novel family of Markov random fields (MRFs), parameterized by a real number \rho \in [0,1]. We then show that applying belief propagation--a well-known ``message-passing'' technique for estimating marginal probabilities--to this family of MRFs recovers a known family of algorithms, ranging from pure survey propagation at one extreme (\rho = 1) to standard belief propagation on the uniform distribution over SAT assignments at the other extreme (\rho = 0). Configurations in these MRFs have a natural interpretation as partial satisfiability assignments, on which a partial order can be defined. We isolate cores as minimal elements in this partial ordering, which are also fixed points of survey propagation and the only assignments with positive probability in the MRF for \rho=1. Our experimental results for k=3 suggest that solutions of random formulas typically do not possess non-trivial cores. This makes it necessary to study the structure of the space of partial assignments for \rho<1 and investigate the role of assignments that are very close to being cores. To that end, we investigate the associated lattice structure, and prove a weight-preserving identity that shows how any MRF with \rho>0 can be viewed as a ``smoothed'' version of the uniform distribution over satisfying assignments (\rho=0). Finally, we isolate properties of Gibbs sampling and message-passing algorithms that are typical for an ensemble of k-SAT problems.


title: Locally connected spanning trees on graphs

abstract: 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.


title: A Digital Signature with Threshold Generation and Verification

abstract: This paper proposes a signature scheme where the signatures are generated by the cooperation of a number of people from a given group of senders and the signatures are verified by a certain number of people from the group of recipients. Shamir's threshold scheme and Schnorr's signature scheme are used to realize the proposed scheme.


title: The strength of replacement in weak arithmetic

abstract: The replacement (or collection or choice) axiom scheme asserts bounded quantifier exchange. We prove the independence of this scheme from various weak theories of arithmetic, sometimes under a complexity assumption.


title: Using a hierarchy of Domain Specific Languages in complex software systems design

abstract: A new design methodology is introduced, with some examples on building Domain Specific Languages hierarchy on top of Scheme.


title: Near Optimal Routing for Small-World Networks with Augmented Local Awareness

abstract: In order to investigate the routing aspects of small-world networks, Kleinberg proposes a network model based on a $d$-dimensional lattice with long-range links chosen at random according to the $d$-harmonic distribution. Kleinberg shows that the greedy routing algorithm by using only local information performs in $O(\log^2 n)$ expected number of hops, where $n$ denotes the number of nodes in the network. Martel and Nguyen have found that the expected diameter of Kleinberg's small-world networks is $\Theta(\log n)$. Thus a question arises naturally: Can we improve the routing algorithms to match the diameter of the networks while keeping the amount of information stored on each node as small as possible? We extend Kleinberg's model and add three augmented local links for each node: two of which are connected to nodes chosen randomly and uniformly within $\log^2 n$ Mahattan distance, and the third one is connected to a node chosen randomly and uniformly within $\log n$ Mahattan distance. We show that if each node is aware of $O(\log n)$ number of neighbors via the augmented local links, there exist both non-oblivious and oblivious algorithms that can route messages between any pair of nodes in $O(\log n \log \log n)$ expected number of hops, which is a near optimal routing complexity and outperforms the other related results for routing in Kleinberg's small-world networks. Our schemes keep only $O(\log^2 n)$ bits of routing information on each node, thus they are scalable with the network size. Besides adding new light to the studies of social networks, our results may also find applications in the design of large-scale distributed networks, such as peer-to-peer systems, in the same spirit of Symphony.


title: PKI Scalability Issues

abstract: This report surveys different PKI technologies such as PKIX and SPKI and the issues of PKI that affect scalability. Much focus is spent on certificate revocation methodologies and status verification systems such as CRLs, Delta-CRLs, CRS, Certificate Revocation Trees, Windowed Certificate Revocation, OCSP, SCVP and DVCS.


title: Outlier Detection by Logic Programming

abstract: The development of effective knowledge discovery techniques has become in the recent few years a very active research area due to the important impact it has in several relevant application areas. One interesting task thereof is that of singling out anomalous individuals from a given population, e.g., to detect rare events in time-series analysis settings, or to identify objects whose behavior is deviant w.r.t. a codified standard set of "social" rules. Such exceptional individuals are usually referred to as outliers in the literature. Recently, outlier detection has also emerged as a relevant KR&R problem. In this paper, we formally state the concept of outliers by generalizing in several respects an approach recently proposed in the context of default logic, for instance, by having outliers not being restricted to single individuals but, rather, in the more general case, to correspond to entire (sub)theories. We do that within the context of logic programming and, mainly through examples, we discuss its potential practical impact in applications. The formalization we propose is a novel one and helps in shedding some light on the real nature of outliers. Moreover, as a major contribution of this work, we illustrate the exploitation of minimality criteria in outlier detection. The computational complexity of outlier detection problems arising in this novel setting is thoroughly investigated and accounted for in the paper as well. Finally, we also propose a rewriting algorithm that transforms any outlier detection problem into an equivalent inference problem under the stable model semantics, thereby making outlier computation effective and realizable on top of any stable model solver.


title: A Generalized Disjunctive Paraconsistent Data Model for Negative and Disjunctive Information

abstract: This paper presents a generalization of the disjunctive paraconsistent relational data model in which disjunctive positive and negative information can be represented explicitly and manipulated. There are situations where the closed world assumption to infer negative facts is not valid or undesirable and there is a need to represent and reason with negation explicitly. We consider explicit disjunctive negation in the context of disjunctive databases as there is an interesting interplay between these two types of information. Generalized disjunctive paraconsistent relation is introduced as the main structure in this model. The relational algebra is appropriately generalized to work on generalized disjunctive paraconsistent relations and their correctness is established.


title: Should Cyberspace Chat Rooms be closed to protect Children?

abstract: The explosion of people networking in cyberspace, disseminating terabytes of information, is being promoted through the use of broadband, bluetooth technology, and wireless mobile computing facilities. New communities within such venues as virtual chat rooms discussion groups, newsgroups etc are being created daily and even hourly. This is raising issues of cyberethics concerning privacy,security, crime, human needs, e-business, e-healthcare, e-government and intellectual property among others that need to be evaluated and reflected upon. With this new freedom come new moral and ethical responsibilities, which raise questions as to whether anything can be published or whether there should be restrictions. This paper addresses one specific area, that has come into the public eye, the closure by Microsoft of all of its free chat rooms.


title: Two Models for the Study of Congested Internet Connections

abstract: In this paper, we introduce two deterministic models aimed at capturing the dynamics of congested Internet connections. The first model is a continuous-time model that combines a system of differential equations with a sudden change in one of the state variables. The second model is a discrete-time model with a time step that arises naturally from the system. Results from these models show good agreement with the well-known ns network simulator, better than the results of a previous, similar model. This is due in large part to the use of the sudden change to reflect the impact of lost data packets. We also discuss the potential use of this model in network traffic state estimation.


title: Proximity Inversion Functions on the Non-Negative Integers

abstract: We consider functions mapping non-negative integers to non-negative real numbers such that a and a+n are mapped to values at least 1/n apart. In this paper we use a novel method to construct such a function. We conjecture that the supremum of the generated function is optimal and pose some unsolved problems.


title: Aperiodic Tilings: Breaking Translational Symmetry

abstract: Classical results on aperiodic tilings are rather complicated and not widely understood. Below, an alternative approach is discussed in hope to provide additional intuition not apparent in classical works.


title: Topics in asynchronous systems

abstract: In the paper we define and characterize the asynchronous systems from the point of view of their autonomy, determinism, order, non-anticipation, time invariance, symmetry, stability and other important properties. The study is inspired by the models of the asynchronous circuits.


title: Capacity-achieving ensembles for the binary erasure channel with bounded complexity

abstract: 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.


title: Bounds on the decoding complexity of punctured codes on graphs

abstract: 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.


title: Incentive Systems in Multi-Level Markets for Virtual Goods

abstract: As an alternative to rigid DRM measures, ways of marketing virtual goods through multi-level or networked marketing have raised some interest. This report is a first approach to multi-level markets for virtual goods from the viewpoint of theoretical economy. A generic, kinematic model for the monetary flow in multi-level markets, which quantitatively describes the incentives that buyers receive through resales revenues, is devised. Building on it, the competition of goods is examined in a dynamical, utility-theoretic model enabling, in particular, a treatment of the free-rider problem. The most important implications for the design of multi-level market mechanisms for virtual goods, or multi-level incentive management systems, are outlined.


title: Efficient polynomial time algorithms computing industrial-strength primitive roots

abstract: E. Bach, following an idea of T. Itoh, has shown how to build a small set of numbers modulo a prime p such that at least one element of this set is a generator of $\pF{p}$\cite{Bach:1997:sppr,Itoh:2001:PPR}. E. Bach suggests also that at least half of his set should be generators. We show here that a slight variant of this set can indeed be made to contain a ratio of primitive roots as close to 1 as necessary. We thus derive several algorithms computing primitive roots correct with very high probability in polynomial time. In particular we present an asymptotically $O^{\sim}(\sqrt{\frac{1}{\epsilon}}log^1.5(p) + \log^2(p))$ algorithm providing primitive roots of $p$ with probability of correctness greater than $1-\epsilon$ and several $O(log^\alpha(p))$, $\alpha \leq 5.23$ algorithms computing "Industrial-strength" primitive roots with probabilities e.g. greater than the probability of "hardware malfunctions".


title: Automatic Generation of CHR Constraint Solvers

abstract: In this paper, we present a framework for automatic generation of CHR solvers given the logical specification of the constraints. This approach takes advantage of the power of tabled resolution for constraint logic programming, in order to check the validity of the rules. Compared to previous works where different methods for automatic generation of constraint solvers have been proposed, our approach enables the generation of more expressive rules (even recursive and splitting rules) that can be used directly as CHR solvers.


title: Field Geology with a Wearable Computer: First Results of the Cyborg Astrobiologist System

abstract: We present results from the first geological field tests of the `Cyborg Astrobiologist', which is a wearable computer and video camcorder system that we are using to test and train a computer-vision system towards having some of the autonomous decision-making capabilities of a field-geologist. The Cyborg Astrobiologist platform has thus far been used for testing and development of these algorithms and systems: robotic acquisition of quasi-mosaics of images, real-time image segmentation, and real-time determination of interesting points in the image mosaics. The hardware and software systems function reliably, and the computer-vision algorithms are adequate for the first field tests. In addition to the proof-of-concept aspect of these field tests, the main result of these field tests is the enumeration of those issues that we can improve in the future, including: dealing with structural shadow and microtexture, and also, controlling the camera's zoom lens in an intelligent manner. Nonetheless, despite these and other technical inadequacies, this Cyborg Astrobiologist system, consisting of a camera-equipped wearable-computer and its computer-vision algorithms, has demonstrated its ability of finding genuinely interesting points in real-time in the geological scenery, and then gathering more information about these interest points in an automated manner.


title: Desynchronization and Speedup in an Asynchronous Conservative Parallel Update Protocol

abstract: In a state-update protocol for a system of $L$ asynchronous parallel processes that communicate only with nearest neighbors, global desynchronization in operation times can be deduced from kinetic roughening of the corresponding virtual-time horizon (VTH). The utilization of the parallel processing environment can be deduced by analyzing the microscopic structure of the VTH. We give an overview of how the methods of non-equilibrium surface growth (physics of complex systems) can be applied to uncover some properties of state update algorithms used in distributed parallel discrete-event simulations (PDES). In particular, we focus on the asynchronous conservative PDES algorithm in a ring communication topology. The time evolution of its VTH is simulated numerically as asynchronous cellular automaton whose update rule corresponds to the update rule followed by this algorithm. We give theoretical estimates of the performance as a function of $L$ and the load per processor, i.e., approximate formulas for the mean speedup and for the desynchronization. It is established that, for a given simulation size, there is a theoretical upper bound for the desynchronization and a theoretical non-zero lower bound for the utilization. The new approach to performance studies, outlined in this chapter, is particularly useful in the search for the design of a new-generation of algorithms that would efficiently carry out an autonomous or tunable synchronization.


title: Mean and Variance Estimation by Kriging

abstract: The aim of the paper is to derive the numerical least-squares estimator for mean and variance of random variable. In order to do so the following questions have to be answered: (i) what is the statistical model for the estimation procedure? (ii) what are the properties of the estimator, like optimality (in which class) or asymptotic properties? (iii) how does the estimator work in practice, how compared to competing estimators?


title: Securing Data in Storage: A Review of Current Research

abstract: 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.


title: Parallel Computing Environments and Methods for Power Distribution System Simulation

abstract: The development of cost-effective highperformance parallel computing on multi-processor supercomputers makes it attractive to port excessively time consuming simulation software from personal computers (PC) to super computes. The power distribution system simulator (PDSS) takes a bottom-up approach and simulates load at the appliance level, where detailed thermal models for appliances are used. This approach works well for a small power distribution system consisting of a few thousand appliances. When the number of appliances increases, the simulation uses up the PC memory and its runtime increases to a point where the approach is no longer feasible to model a practical large power distribution system. This paper presents an effort made to port a PC-based power distribution system simulator to a 128-processor shared-memory supercomputer. The paper offers an overview of the parallel computing environment and a description of the modification made to the PDSS model. The performance of the PDSS running on a standalone PC and on the supercomputer is compared. Future research direction of utilizing parallel computing in the power distribution system simulation is also addressed.


title: A Directed Signature Scheme and its Applications

abstract: This paper presents a directed signature scheme with the property that the signature can be verified only with the help of signer or signature receiver. We also propose its applications to share verification of signatures and to threshold cryptosystems.


title: Business Processes: The Theoretical Impact of Process Thinking on Information Systems Development

abstract: This paper investigates two aspects of process thinking that affect the success rate of IT projects. These two aspects are the changes in the structure of organizations and the epistemology of Information Systems Development. Firstly, the conception of business processes within the management of organizations increases the structural complexity of Information Systems, because existing systems have to be integrated into a coherent cross-functional architecture. Secondly, process thinking leads to a particular view of organizations that ultimately has a negative effect on the support of Information Systems. As an illustration of process thinking, the Business Process Reengineering movement adheres to a technocratic management perspective of organizations. Particularly this conception of organization views people as mechanisms to realize certain organizational goals. As a result of this view stakeholders are confronted with the implemented systems, rather than consulted about the scope and functionality of those systems. Therefore, both aspects of process thinking have a negative impact on the success of IT projects. The problem of structural complexity is an area that is addressed by Enterprise Application Integration, and mainly requires technical solutions. However, the problems associated with the conception of organization require a different, markedly non-technical, perspective. Several directions are discussed to overcome some limitations of process thinking, but these directions are merely small pointers. If truly effective and useful Information Systems are to be acquired, IT practitioners and scientists require a completely different mindset.


title: Checking modes of HAL programs

abstract: Recent constraint logic programming (CLP) languages, such as HAL and Mercury, require type, mode and determinism declarations for predicates. This information allows the generation of efficient target code and the detection of many errors at compile-time. Unfortunately, mode checking in such languages is difficult. One of the main reasons is that, for each predicate mode declaration, the compiler is required to appropriately re-order literals in the predicate's definition. The task is further complicated by the need to handle complex instantiations (which interact with type declarations and higher-order predicates) and automatic initialization of solver variables. Here we define mode checking for strongly typed CLP languages which require reordering of clause body literals. In addition, we show how to handle a simple case of polymorphic modes by using the corresponding polymorphic types.


title: NP - P is not empty

abstract: We present the MEoP problem that decides the existence of solutions to certain modular equations over prime numbers and show how this separates the complexity class NP from its subclass P


title: Unification of Fusion Theories

abstract: 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.


title: Four Principles Fundamental to Design Practice for Human Centred Systems

abstract: A Survey of the principal literature on Human Centred Design reveals the four most referenced principles. These are discussed with reference to the application of a particular website, and a user survey is constructed based upon the four principles.


title: A new architecture for making highly scalable applications

abstract: An application is a logical image of the world on a computer. A scalable application is an application that allows one to update that logical image at run time. To put it in operational terms: an application is scalable if a client can change between time T1 and time T2 - the logic of the application as expressed by language L; - the structure and volume of the stored knowledge; - the user interface of the application; while clients working with the application at time T1 will work with the changed application at time T2 without performing any special action between T1 and T2. In order to realize such a scalable application a new architecture has been developed that fully orbits around language. In order to verify the soundness of that architecture a program has been build. Both architecture and program are called CommunSENS. The main purpose of this paper is: - to list the relevant elements of the architecture; - to give a visual presentation of how the program and its image of the world look like; - to give a visual presentation of how the image can be updated. Some relevant philosophical and practical backgrounds are included in the appendixes.


title: Inapproximability of Combinatorial Optimization Problems

abstract: We survey results on the hardness of approximating combinatorial optimization problems.


title: Some Applications of Coding Theory in Computational Complexity

abstract: 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.


title: Augmenting ALC(D) (atemporal) roles and (aspatial) concrete domain with temporal roles and a spatial concrete domain -first results

abstract: We consider the well-known family ALC(D) of description logics with a concrete domain, and provide first results on a framework obtained by augmenting ALC(D) atemporal roles and aspatial concrete domain with temporal roles and a spatial concrete domain.


title: A TCSP-like decidable constraint language generalising existing cardinal direction relations

abstract: We define a quantitative constraint language subsuming two calculi well-known in QSR (Qualitative Spatial Reasoning): Frank's cone-shaped and projection-based calculi of cardinal direction relations. We show how to solve a CSP (Constraint Satisfaction Problem) expressed in the language.


title: An ALC(D)-based combination of temporal constraints and spatial constraints suitable for continuous (spatial) change

abstract: We present a family of spatio-temporal theories suitable for continuous spatial change in general, and for continuous motion of spatial scenes in particular. The family is obtained by spatio-temporalising the well-known ALC(D) family of Description Logics (DLs) with a concrete domain D, as follows, where TCSPs denotes "Temporal Constraint Satisfaction Problems", a well-known constraint-based framework: (1) temporalisation of the roles, so that they consist of TCSP constraints (specifically, of an adaptation of TCSP constraints to interval variables); and (2) spatialisation of the concrete domain D: the concrete domain is now $D_x$, and is generated by a spatial Relation Algebra (RA) $x$, in the style of the Region-Connection Calculus RCC8. We assume durative truth (i.e., holding during a durative interval). We also assume the homogeneity property (if a truth holds during a given interval, it holds during all of its subintervals). Among other things, these assumptions raise the "conflicting" problem of overlapping truths, which the work solves with the use of a specific partition of the 13 atomic relations of Allen's interval algebra.


title: FORM Matters: Fast Symbolic Computation under UNIX

abstract: We give a brief introduction to FORM, a symbolic programming language for massive batch operations, designed by J.A.M. Vermaseren. In particular, we stress various methods to efficiently use FORM under the UNIX operating system. Several scripts and examples are given, and suggestions on how to use the vim editor as development platform.


title: A Directed -Threshold Multi-Signature Scheme

abstract: In this paper, we propose a Directed Threshold Multi-Signature Scheme. In this threshold signature scheme, any malicious set of signers cannot impersonate any other set of signers to forge the signatures. In case of forgery, it is possible to trace the signing set. This threshold signature scheme is applicable when the message is sensitive to the signature receiver; and the signatures are generated by the cooperation of a number of people from a given group of senders.


title: Some Applications of Directed Signature Scheme

abstract: Directed signature scheme is applicable when the signed message contains information sensitive to the receiver, because only receiver can directly verify the signature and that he/she can prove its validity to any third party, whenever necessary. This paper presents two applications of directed signature scheme. (i) Directed –Delegated Signature Scheme. This scheme combines the idea of proxy signatures with directed signature scheme. (ii) Allocation of registration number. This scheme proposes a registration scheme in which the registration number cannot be forged and misused.


title: Quantum Complexity Classes

abstract: In our thesis, we try to shed more light onto the complexity of quantum complexity classes by refining the related part of the hierarchy. First, we review the basic concepts of quantum computing in general. Then, inspired by BQP, we define new complexity classes. They are placed between BPP and PSPACE. We show that they incorporate the current important quantum algorithms. Furthermore, the importance of the unitarity constraint given by quantum mechanics is revealed. Without this requirement, we naturally arrive at the class AWPP, which was up to now thought to be just an artificially defined class. We hope that some of our newly defined classes could find their use in proving results about BQP.


title: Better Quasi-Ordered Transition Systems

abstract: Many existing algorithms for model checking of infinite-state systems operate on constraints which are used to represent (potentially infinite) sets of states. A general powerful technique which can be employed for proving termination of these algorithms is that of well quasi-orderings. Several methodologies have been proposed for derivation of new well quasi-ordered constraint systems. However, many of these constraint systems suffer from a "constraint explosion problem", as the number of the generated constraints grows exponentially with the size of the problem. In this paper, we demonstrate that a refinement of the theory of well quasi-orderings, called the theory of better quasi-orderings, is more appropriate for symbolic model checking, since it allows inventing constraint systems which are both well quasi-ordered and compact. As a main application, we introduce existential zones, a constraint system for verification of systems with unboundedly many clocks and use our methodology to prove that existential zones are better quasi-ordered. We show how to use existential zones in verification of timed Petri nets and present some experimental results. Also, we apply our methodology to derive new constraint systems for verification of broadcast protocols, lossy channel systems, and integral relational automata. The new constraint systems are exponentially more succinct than existing ones, and their well quasi-ordering cannot be shown by previous methods in the literature.


title: On the role of MMSE estimation in approaching the information-theoretic limits of linear Gaussian channels: Shannon meets Wiener

abstract: We discuss why MMSE estimation arises in lattice-based schemes for approaching the capacity of linear Gaussian channels, and comment on its properties.


title: An Approximation Algorithm for Stackelberg Network Pricing

abstract: 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.


title: The Building of Online Communities: An approach for learning organizations, with a particular focus on the museum sector

abstract: This paper considers the move toward and potential of building online communities, with a particular focus on the museum sector. For instance, the increase in the use of `personalized' toolkits that are becoming an integral part of the online presence for learning organizations, like museums, can provide a basis for creating and sustaining communities. A set of case studies further illustrates working examples of the ways in which personalization and specific tools are developing collaborative spaces, community channels and group interactions.


title: Using sparse matrices and splines-based interpolation in computational fluid dynamics simulations

abstract: In this relation I present a technique of construction and fast evaluation of a family of cubic polynomials for analytic smoothing and graphical rendering of particles trajectories for flows in a generic geometry. The principal result of the work was implementation and test of a method for interpolating 3D points by regular parametric curves and their fast and efficient evaluation for a good resolution of rendering. For the purpose a parallel environment using a multiprocessor cluster architecture has been used. This work has been developed for the Research and Development Department of my company for planning advanced customized models of industrial burners.


title: Fast Construction of Nets in Low Dimensional Metrics, and Their Applications

abstract: We present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain improved algorithms for the following problems: Approximate nearest neighbor search, well-separated pair decomposition, compact representation scheme, doubling measure, and computation of the (approximate) Lipschitz constant of a function. In all cases, the running (preprocessing) time is near-linear and the space being used is linear.


title: A Sentimental Education: Sentiment Analysis Using Subjectivity Summarization Based on Minimum Cuts

abstract: Sentiment analysis seeks to identify the viewpoint(s) underlying a text span; an example application is classifying a movie review as "thumbs up" or "thumbs down". To determine this sentiment polarity, we propose a novel machine-learning method that applies text-categorization techniques to just the subjective portions of the document. Extracting these portions can be implemented using efficient techniques for finding minimum cuts in graphs; this greatly facilitates incorporation of cross-sentence contextual constraints.


title: From Digital Television to Internet?

abstract: This paper provides a general technical overview of the Multimedia Home Platform (MHP) specifications. MHP is a generic interface between digital applications and user machines, whether they happen to be set top boxes, digital TV sets or Multimedia PC's. MHP extends the DVB open standards. Addressed are MHP architexture, System core and MHP Profiles.


title: The Infati Data

abstract: The ability to perform meaningful empirical studies is of essence in research in spatio-temporal query processing. Such studies are often necessary to gain detailed insight into the functional and performance characteristics of proposals for new query processing techniques. We present a collection of spatio-temporal data, collected during an intelligent speed adaptation project, termed INFATI, in which some two dozen cars equipped with GPS receivers and logging equipment took part. We describe how the data was collected and how it was "modified" to afford the drivers some degree of anonymity. We also present the road network in which the cars were moving during data collection. The GPS data is publicly available for non-commercial purposes. It is our hope that this resource will help the spatio-temporal research community in its efforts to develop new and better query processing techniques.


title: Shannon Information and Kolmogorov Complexity

abstract: We compare the elementary theories of Shannon information and Kolmogorov complexity, the extent to which they have a common purpose, and where they are fundamentally different. We discuss and relate the basic notions of both theories: Shannon entropy versus Kolmogorov complexity, the relation of both to universal coding, Shannon mutual information versus Kolmogorov (`algorithmic') mutual information, probabilistic sufficient statistic versus algorithmic sufficient statistic (related to lossy compression in the Shannon theory versus meaningful information in the Kolmogorov theory), and rate distortion theory versus Kolmogorov's structure function. Part of the material has appeared in print before, scattered through various publications, but this is the first comprehensive systematic comparison. The last mentioned relations are new.


title: Capacity and Random-Coding Exponents for Channel Coding with Side Information

abstract: Capacity formulas and random-coding exponents are derived for a generalized family of Gel'fand-Pinsker coding problems. These exponents yield asymptotic upper bounds on the achievable log probability of error. In our model, information is to be reliably transmitted through a noisy channel with finite input and output alphabets and random state sequence, and the channel is selected by a hypothetical adversary. Partial information about the state sequence is available to the encoder, adversary, and decoder. The design of the transmitter is subject to a cost constraint. Two families of channels are considered: 1) compound discrete memoryless channels (CDMC), and 2) channels with arbitrary memory, subject to an additive cost constraint, or more generally to a hard constraint on the conditional type of the channel output given the input. Both problems are closely connected. The random-coding exponent is achieved using a stacked binning scheme and a maximum penalized mutual information decoder, which may be thought of as an empirical generalized Maximum a Posteriori decoder. For channels with arbitrary memory, the random-coding exponents are larger than their CDMC counterparts. Applications of this study include watermarking, data hiding, communication in presence of partially known interferers, and problems such as broadcast channels, all of which involve the fundamental idea of binning.


title: Applying Policy Iteration for Training Recurrent Neural Networks

abstract: 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.


title: A dynamical model of a GRID market

abstract: 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.


title: Demo or Practice: Critical Analysis of the Language/Action Perspective

abstract: 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.


title: A Shared Write-protected Root Filesystem for a Group of Networked Clients

abstract: A method to boot a cluster of diskless network clients from a single write-protected NFS root file system is shown. The problems encountered when first implementing the setup and their solution are discussed. Finally, the setup is briefly compared to using a kernel-embedded root file system.


title: Source Coding with Fixed Lag Side Information

abstract: We consider source coding with fixed lag side information at the decoder. We focus on the special case of perfect side information with unit lag corresponding to source coding with feedforward (the dual of channel coding with feedback) introduced by Pradhan. We use this duality to develop a linear complexity algorithm which achieves the rate-distortion bound for any memoryless finite alphabet source and distortion measure.


title: Diffusive Load Balancing of Loosely-Synchronous Parallel Programs over Peer-to-Peer Networks

abstract: The use of under-utilized Internet resources is widely recognized as a viable form of high performance computing. Sustained processing power of roughly 40T FLOPS using 4 million volunteered Internet hosts has been reported for embarrassingly parallel problems. At the same time, peer-to-peer (P2P) file sharing networks, with more than 50 million participants, have demonstrated the capacity for scale in distributed systems. This paper contributes a study of load balancing techniques for a general class of loosely-synchronous parallel algorithms when executed over a P2P network. We show that decentralized, diffusive load balancing can be effective at balancing load and is facilitated by the dynamic properties of P2P. While a moderate degree of dynamicity can benefit load balancing, significant dynamicity hinders the parallel program performance due to the need for increased load migration. To the best of our knowledge this study provides new insight into the performance of loosely-synchronous parallel programs over the Internet.


title: A New Proxy Ring Signature Scheme

abstract: 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.


title: Comment on A dynamic ID-based Remote User Authentication Scheme

abstract: Since 1981, when Lamport introduced the remote user authentication scheme using table, a plenty of schemes had been proposed with tables or without table using. Recently Das et al. proposed a dynamic id-based remote user authentication scheme. They claimed that their scheme is secure against ID-theft, and can resist the reply attacks, forgery attacks, insider attacks an so on. In this paper we show that Das et al's scheme is completly insecure and using of this scheme is like an open server access without password.


title: DiPerF: an automated DIstributed PERformance testing Framework

abstract: 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.


title: Fibonacci connection between Huffman codes and Wythoff array

abstract: Fibonacci connection between non-decreasing sequences of positive integers producing maximum height Huffman trees and the Wythoff array has been proved.


title: Normal forms for Answer Sets Programming

abstract: Normal forms for logic programs under stable/answer set semantics are introduced. We argue that these forms can simplify the study of program properties, mainly consistency. The first normal form, called the {\em kernel} of the program, is useful for studying existence and number of answer sets. A kernel program is composed of the atoms which are undefined in the Well-founded semantics, which are those that directly affect the existence of answer sets. The body of rules is composed of negative literals only. Thus, the kernel form tends to be significantly more compact than other formulations. Also, it is possible to check consistency of kernel programs in terms of colorings of the Extended Dependency Graph program representation which we previously developed. The second normal form is called {\em 3-kernel.} A 3-kernel program is composed of the atoms which are undefined in the Well-founded semantics. Rules in 3-kernel programs have at most two conditions, and each rule either belongs to a cycle, or defines a connection between cycles. 3-kernel programs may have positive conditions. The 3-kernel normal form is very useful for the static analysis of program consistency, i.e., the syntactic characterization of existence of answer sets. This result can be obtained thanks to a novel graph-like representation of programs, called Cycle Graph which presented in the companion article \cite{Cos04b}.


title: L1 regularization is better than L2 for learning and predicting chaotic systems

abstract: Emergent behaviors are in the focus of recent research interest. It is then of considerable importance to investigate what optimizations suit the learning and prediction of chaotic systems, the putative candidates for emergence. We have compared L1 and L2 regularizations on predicting chaotic time series using linear recurrent neural networks. The internal representation and the weights of the networks were optimized in a unifying framework. Computational tests on different problems indicate considerable advantages for the L1 regularization: It had considerably better learning time and better interpolating capabilities. We shall argue that optimization viewed as a maximum likelihood estimation justifies our results, because L1 regularization fits heavy-tailed distributions -- an apparently general feature of emergent systems -- better.


title: HEP@Home - A distributed computing system based on BOINC

abstract: Project SETI@HOME has proven to be one of the biggest successes of distributed computing during the last years. With a quite simple approach SETI manages to process large volumes of data using a vast amount of distributed computer power. To extend the generic usage of this kind of distributed computing tools, BOINC is being developed. In this paper we propose HEP@HOME, a BOINC version tailored to the specific requirements of the High Energy Physics (HEP) community. The HEP@HOME will be able to process large amounts of data using virtually unlimited computing power, as BOINC does, and it should be able to work according to HEP specifications. In HEP the amounts of data to be analyzed or reconstructed are of central importance. Therefore, one of the design principles of this tool is to avoid data transfer. This will allow scientists to run their analysis applications and taking advantage of a large number of CPUs. This tool also satisfies other important requirements in HEP, namely, security, fault-tolerance and monitoring.


title: Automated Pattern Detection--An Algorithm for Constructing Optimally Synchronizing Multi-Regular Language Filters

abstract: 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 $\sigma$ and a collection $\{\mc{D}_i\}$ of finite automata, identify the regions of $\sigma$ 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 $\sigma$'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.

categories: cs.CV cond-mat.stat-mech cs.CL cs.DS cs.IR cs.LG nlin.AO nlin.CG nlin.PS physics.comp-ph q-bio.GN


title: Utilitarian resource assignment

abstract: This paper studies a resource allocation problem introduced by Koutsoupias and Papadimitriou. The scenario is modelled as a multiple-player game in which each player selects one of a finite number of known resources. The cost to the player is the total weight of all players who choose that resource, multiplied by the ``delay'' of that resource. Recent papers have studied the Nash equilibria and social optima of this game in terms of the $L_\infty$ cost metric, in which the social cost is taken to be the maximum cost to any player. We study the $L_1$ variant of this game, in which the social cost is taken to be the sum of the costs to the individual players, rather than the maximum of these costs. We give bounds on the size of the coordination ratio, which is the ratio between the social cost incurred by selfish behavior and the optimal social cost; we also study the algorithmic problem of finding optimal (lowest-cost) assignments and Nash Equilibria. Additionally, we obtain bounds on the ratio between alternative Nash equilibria for some special cases of the problem.


title: Finite-Length Scaling and Finite-Length Shift for Low-Density Parity-Check Codes

abstract: Consider communication over the binary erasure channel BEC using random low-density parity-check codes with finite-blocklength n from `standard' ensembles. We show that large error events is conveniently described within a scaling theory, and explain how to estimate heuristically their effect. Among other quantities, we consider the finite length threshold e(n), defined by requiring a block error probability P_B = 1/2. For ensembles with minimum variable degree larger than two, the following expression is argued to hold e(n) = e -e_1 n^{-2/3} +\Theta(n^{-1}) with a calculable shift} parameter e_1>0.


title: Adaptive Cluster Expansion (ACE): A Hierarchical Bayesian Network

abstract: 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.


title: Complexity Results in Graph Reconstruction

abstract: 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.


title: RRL: A Rich Representation Language for the Description of Agent Behaviour in NECA

abstract: 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


title: All Superlinear Inverse Schemes are coNP-Hard

abstract: How hard is it to invert NP-problems? We show that all superlinearly certified inverses of NP problems are coNP-hard. To do so, we develop a novel proof technique that builds diagonalizations against certificates directly into a circuit.


title: The Key Authority - Secure Key Management in Hierarchical Public Key Infrastructures

abstract: We model a private key`s life cycle as a finite state machine. The states are the key`s phases of life and the transition functions describe tasks to be done with the key. Based on this we define and describe the key authority, a trust center module, which potentiates the easy enforcement of secure management of private keys in hierarchical public key infrastructures. This is done by assembling all trust center tasks concerning the crucial handling of private keys within one centralized module. As this module resides under full control of the trust center`s carrier it can easily be protected by well-known organizational and technical measures.


title: Outflanking and securely using the PIN/TAN-System

abstract: The PIN/TAN-system is an authentication and authorization scheme used in e-business. Like other similar schemes it is successfully attacked by criminals. After shortly classifying the various kinds of attacks we accomplish malicious code attacks on real World Wide Web transaction systems. In doing so we find that it is really easy to outflank these systems. This is even supported by the users' behavior. We give a few simple behavior rules to improve this situation. But their impact is limited. Also the providers support the attacks by having implementation flaws in their installations. Finally we show that the PIN/TAN-system is not suitable for usage in highly secure applications.


title: Lattice QCD Data and Metadata Archives at Fermilab and the International Lattice Data Grid

abstract: 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.


title: Detecting User Engagement in Everyday Conversations

abstract: This paper presents a novel application of speech emotion recognition: estimation of the level of conversational engagement between users of a voice communication system. We begin by using machine learning techniques, such as the support vector machine (SVM), to classify users' emotions as expressed in individual utterances. However, this alone fails to model the temporal and interactive aspects of conversational engagement. We therefore propose the use of a multilevel structure based on coupled hidden Markov models (HMM) to estimate engagement levels in continuous natural speech. The first level is comprised of SVM-based classifiers that recognize emotional states, which could be (e.g.) discrete emotion types or arousal/valence levels. A high-level HMM then uses these emotional states as input, estimating users' engagement in conversation by decoding the internal states of the HMM. We report experimental results obtained by applying our algorithms to the LDC Emotional Prosody and CallFriend speech corpora.


title: Life Above Threshold: From List Decoding to Area Theorem and MSE

abstract: 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.


title: Nondeterministic Linear Logic

abstract: In this paper, we introduce Linear Logic with a nondeterministic facility, which has a self-dual additive connective. In the system the proof net technology is available in a natural way. The important point is that nondeterminism in the system is expressed by the process of normalization, not by proof search. Moreover we can incorporate the system into Light Linear Logic and Elementary Linear Logic developed by J.-Y.Girard recently: Nondeterministic Light Linear Logic and Nondeterministic Elementary Linear Logic are defined in a very natural way.


title: Weak Typed Boehm Theorem on IMLL

abstract: In the Boehm theorem workshop on Crete island, Zoran Petric called Statman's ``Typical Ambiguity theorem'' typed Boehm theorem. Moreover, he gave a new proof of the theorem based on set-theoretical models of the simply typed lambda calculus. In this paper, we study the linear version of the typed Boehm theorem on a fragment of Intuitionistic Linear Logic. We show that in the multiplicative fragment of intuitionistic linear logic without the multiplicative unit 1 (for short IMLL) weak typed Boehm theorem holds. The system IMLL exactly corresponds to the linear lambda calculus without exponentials, additives and logical constants. The system IMLL also exactly corresponds to the free symmetric monoidal closed category without the unit object. As far as we know, our separation result is the first one with regard to these systems in a purely syntactical manner.


title: Similarity-Based Supervisory Control of Discrete Event Systems

abstract: Due to the appearance of uncontrollable events in discrete event systems, one may wish to replace the behavior leading to the uncontrollability of pre-specified language by some quite similar one. To capture this similarity, we introduce metric to traditional supervisory control theory and generalize the concept of original controllability to $\ld$-controllability, where $\ld$ indicates the similarity degree of two languages. A necessary and sufficient condition for a language to be $\ld$-controllable is provided. We then examine some properties of $\ld$-controllable languages and present an approach to optimizing a realization.


title: The state complexity of L^2 and L^k

abstract: We show that if M is a DFA with n states over an arbitrary alphabet and L = L(M), then the worst-case state complexity of L^2 is n*2^n - 2^{n-1}. If, however, M is a DFA over a unary alphabet, then the worst-case state complexity of L^k is kn-k+1 for all k >= 2.


title: An In-Depth Look at Information Fusion Rules & the Unification of Fusion Theories

abstract: This paper may look like a glossary of the fusion rules and we also introduce new ones presenting their formulas and examples: Conjunctive, Disjunctive, Exclusive Disjunctive, Mixed Conjunctive-Disjunctive rules, Conditional rule, Dempster's, Yager's, Smets' TBM rule, Dubois-Prade's, Dezert-Smarandache classical and hybrid rules, Murphy's average rule, Inagaki-Lefevre-Colot-Vannoorenberghe Unified Combination rules [and, as particular cases: Iganaki's parameterized rule, Weighting Average Operator, minC (M. Daniel), and newly Proportional Conflict Redistribution rules (Smarandache-Dezert) among which PCR5 is the most exact way of redistribution of the conflicting mass to non-empty sets following the path of the conjunctive rule], Zhang's Center Combination rule, Convolutive x-Averaging, Consensus Operator (Josang), Cautious Rule (Smets), ?-junctions rules (Smets), etc. and three new T-norm & T-conorm rules adjusted from fuzzy and neutrosophic sets to information fusion (Tchamova-Smarandache). Introducing the degree of union and degree of inclusion with respect to the cardinal of sets not with the fuzzy set point of view, besides that of intersection, many fusion rules can be improved. There are corner cases where each rule might have difficulties working or may not get an expected result.


title: P-time Completeness of Light Linear Logic and its Nondeterministic Extension

abstract: In CSL'99 Roversi pointed out that the Turing machine encoding of Girard's seminal paper "Light Linear Logic" has a flaw. Moreover he presented a working version of the encoding in Light Affine Logic, but not in Light Linear Logic. In this paper we present a working version of the encoding in Light Linear Logic. The idea of the encoding is based on a remark of Girard's tutorial paper on Linear Logic. The encoding is also an example which shows usefulness of additive connectives. Moreover we also consider a nondeterministic extension of Light Linear Logic. We show that the extended system is NP-complete in the same meaning as P-completeness of Light Linear Logic.


title: Overhead-Free Computation, DCFLs, and CFLs

abstract: We study Turing machines that are allowed absolutely no space overhead. The only work space the machines have, beyond the fixed amount of memory implicit in their finite-state control, is that which they can create by cannibalizing the input bits' own space. This model more closely reflects the fixed-sized memory of real computers than does the standard complexity-theoretic model of linear space. Though some context-sensitive languages cannot be accepted by such machines, we show that all context-free languages can be accepted nondeterministically in polynomial time with absolutely no space overhead, and that all deterministic context-free languages can be accepted deterministically in polynomial time with absolutely no space overhead.


title: Self-Organised Factorial Encoding of a Toroidal Manifold

abstract: It is shown analytically how a neural network can be used optimally to encode input data that is derived from a toroidal manifold. The case of a 2-layer network is considered, where the output is assumed to be a set of discrete neural firing events. The network objective function measures the average Euclidean error that occurs when the network attempts to reconstruct its input from its output. This optimisation problem is solved analytically for a toroidal input manifold, and two types of solution are obtained: a joint encoder in which the network acts as a soft vector quantiser, and a factorial encoder in which the network acts as a pair of soft vector quantisers (one for each of the circular subspaces of the torus). The factorial encoder is favoured for small network sizes when the number of observed firing events is large. Such self-organised factorial encoding may be used to restrict the size of network that is required to perform a given encoding task, and will decompose an input manifold into its constituent submanifolds.


title: Hardware-Oriented Group Solutions for Hard Problems

abstract: Group and individual solutions are considered for hard problems such as satisfiability problem. Time-space trade-off in a structured active memory provides means to achieve lower time complexity for solutions of these problems.


title: Frequent Knot Discovery

abstract: We explore the possibility of applying the framework of frequent pattern mining to a class of continuous objects appearing in nature, namely knots. We introduce the frequent knot mining problem and present a solution. The key observation is that a database consisting of knots can be transformed into a transactional database. This observation is based on the Prime Decomposition Theorem of knots.


title: Generating All Maximal Induced Subgraphs for Hereditary, Connected-Hereditary and Rooted-Hereditary Properties

abstract: The problem of computing all maximal induced subgraphs of a graph G that have a graph property P, also called the maximal P-subgraphs problem, is considered. This problem is studied for hereditary, connected-hereditary and rooted-hereditary graph properties. The maximal P-subgraphs problem is reduced to restricted versions of this problem by providing algorithms that solve the general problem, assuming that an algorithm for a restricted version is given. The complexity of the algorithms are analyzed in terms of total polynomial time, incremental polynomial time and the complexity class P-enumerable. The general results presented allow simple proofs that the maximal P-subgraphs problem can be solved efficiently (in terms of the input and output) for many different properties.


title: Two Methods for Decreasing the Computational Complexity of the MIMO ML Decoder

abstract: We propose use of QR factorization with sort and Dijkstra's algorithm for decreasing the computational complexity of the sphere decoder that is used for ML detection of signals on the multi-antenna fading channel. QR factorization with sort decreases the complexity of searching part of the decoder with small increase in the complexity required for preprocessing part of the decoder. Dijkstra's algorithm decreases the complexity of searching part of the decoder with increase in the storage complexity. The computer simulation demonstrates that the complexity of the decoder is reduced by the proposed methods significantly.


title: Maximum Mutual Information of Space-Time Block Codes with Symbolwise Decodability

abstract: In this paper, we analyze the performance of space-time block codes which enable symbolwise maximum likelihood decoding. We derive an upper bound of maximum mutual information (MMI) on space-time block codes that enable symbolwise maximum likelihood decoding for a frequency non-selective quasi-static fading channel. MMI is an upper bound on how much one can send information with vanishing error probability by using the target code.


title: Neural Architectures for Robot Intelligence

abstract: We argue that the direct experimental approaches to elucidate the architecture of higher brains may benefit from insights gained from exploring the possibilities and limits of artificial control architectures for robot systems. We present some of our recent work that has been motivated by that view and that is centered around the study of various aspects of hand actions since these are intimately linked with many higher cognitive abilities. As examples, we report on the development of a modular system for the recognition of continuous hand postures based on neural nets, the use of vision and tactile sensing for guiding prehensile movements of a multifingered hand, and the recognition and use of hand gestures for robot teaching. Regarding the issue of learning, we propose to view real-world learning from the perspective of data mining and to focus more strongly on the imitation of observed actions instead of purely reinforcement-based exploration. As a concrete example of such an effort we report on the status of an ongoing project in our lab in which a robot equipped with an attention system with a neurally inspired architecture is taught actions by using hand gestures in conjunction with speech commands. We point out some of the lessons learnt from this system, and discuss how systems of this kind can contribute to the study of issues at the junction between natural and artificial cognitive systems.


title: Strategy in Ulam's Game and Tree Code Give Error-Resistant Protocols

abstract: We present a new approach to construction of protocols which are proof against communication errors. The construction is based on a generalization of the well known Ulam's game. We show equivalence between winning strategies in this game and robust protocols for multi-party computation. We do not give any complete theory. We want rather to describe a new fresh idea. We use a tree code defined by Schulman. The tree code is the most important part of the interactive version of Shannon's Coding Theorem proved by Schulman. He uses probabilistic argument for the existence of a tree code without giving any effective construction. We show another proof yielding a randomized construction which in contrary to his proof almost surely gives a good code. Moreover our construction uses much smaller alphabet.


title: An Example of Clifford Algebras Calculations with GiNaC

abstract: This example of Clifford algebras calculations uses GiNaC (http://www.ginac.de/) library, which includes a support for generic Clifford algebra starting from version~1.3.0. Both symbolic and numeric calculation are possible and can be blended with other functions of GiNaC. This calculations was made for the paper math.CV/0410399. Described features of GiNaC are already available at PyGiNaC (http://sourceforge.net/projects/pyginac/) and due to course should propagate into other software like GNU Octave (http://www.octave.org/), gTybalt (http://www.fis.unipr.it/~stefanw/gtybalt.html), which use GiNaC library as their back-end.


title: Analysis of and workarounds for element reversal for a finite element-based algorithm for warping triangular and tetrahedral meshes

abstract: We consider an algorithm called FEMWARP for warping triangular and tetrahedral finite element meshes that computes the warping using the finite element method itself. The algorithm takes as input a two- or three-dimensional domain defined by a boundary mesh (segments in one dimension or triangles in two dimensions) that has a volume mesh (triangles in two dimensions or tetrahedra in three dimensions) in its interior. It also takes as input a prescribed movement of the boundary mesh. It computes as output updated positions of the vertices of the volume mesh. The first step of the algorithm is to determine from the initial mesh a set of local weights for each interior vertex that describes each interior vertex in terms of the positions of its neighbors. These weights are computed using a finite element stiffness matrix. After a boundary transformation is applied, a linear system of equations based upon the weights is solved to determine the final positions of the interior vertices. The FEMWARP algorithm has been considered in the previous literature (e.g., in a 2001 paper by Baker). FEMWARP has been succesful in computing deformed meshes for certain applications. However, sometimes FEMWARP reverses elements; this is our main concern in this paper. We analyze the causes for this undesirable behavior and propose several techniques to make the method more robust against reversals. The most successful of the proposed methods includes combining FEMWARP with an optimization-based untangler.


title: A Note on Scheduling Equal-Length Jobs to Maximize Throughput

abstract: We study the problem of scheduling equal-length jobs with release times and deadlines, where the objective is to maximize the number of completed jobs. Preemptions are not allowed. In Graham's notation, the problem is described as 1|r_j;p_j=p|\sum U_j. We give the following results: (1) We show that the often cited algorithm by Carlier from 1981 is not correct. (2) We give an algorithm for this problem with running time O(n^5).


title: Simple Distributed Weighted Matchings

abstract: Wattenhofer [WW04] derive a complicated distributed algorithm to compute a weighted matching of an arbitrary weighted graph, that is at most a factor 5 away from the maximum weighted matching of that graph. We show that a variant of the obvious sequential greedy algorithm [Pre99], that computes a weighted matching at most a factor 2 away from the maximum, is easily distributed. This yields the best known distributed approximation algorithm for this problem so far.


title: Worst-Case Optimal Tree Layout in External Memory

abstract: Consider laying out a fixed-topology tree of N nodes into external memory with block size B so as to minimize the worst-case number of block memory transfers required to traverse a path from the root to a node of depth D. We prove that the optimal number of memory transfers is $$ \cases{ \displaystyle \Theta\left( {D \over \lg (1{+}B)} \right) & when $D = O(\lg N)$, \cr \displaystyle \Theta\left( {\lg N \over \lg \left(1{+}{B \lg N \over D}\right)} \right) & when $D = \Omega(\lg N)$ and $D = O(B \lg N)$, \cr \displaystyle \Theta\left( {D \over B} \right) & when $D = \Omega(B \lg N)$. } $$


title: Intransitivity and Vagueness

abstract: 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.


title: Sleeping Beauty Reconsidered: Conditioning and Reflection in Asynchronous Systems

abstract: A careful analysis of conditioning in the Sleeping Beauty problem is done, using the formal model for reasoning about knowledge and probability developed by Halpern and Tuttle. While the Sleeping Beauty problem has been viewed as revealing problems with conditioning in the presence of imperfect recall, the analysis done here reveals that the problems are not so much due to imperfect recall as to asynchrony. The implications of this analysis for van Fraassen's Reflection Principle and Savage's Sure-Thing Principle are considered.


title: Turing Machine with Faults, Failures and Recovery

abstract: A Turing machine with faults, failures and recovery (TMF) is described. TMF is (weakly) non-deterministic Turing machine consisting of five semi-infinite tapes (Master Tape, Synchro Tape, Backup Tape, Backup Synchro Tape, User Tape) and four controlling components (Program, Daemon, Apparatus, User). Computational process consists of three phases (Program Phase, Failure Phase, Repair Phase). C++ Simulator of a Turing machine with faults, failures and recovery has been developed.


title: A 2-chain can interlock with a k-chain

abstract: One of the open problems posed in [3] is: what is the minimal number k such that an open, flexible k-chain can interlock with a flexible 2-chain? In this paper, we establish the assumption behind this problem, that there is indeed some k that achieves interlocking. We prove that a flexible 2-chain can interlock with a flexible, open 16-chain.


title: An Extended Generalized Disjunctive Paraconsistent Data Model for Disjunctive Information

abstract: This paper presents an extension of generalized disjunctive paraconsistent relational data model in which pure disjunctive positive and negative information as well as mixed disjunctive positive and negative information can be represented explicitly and manipulated. We consider explicit mixed disjunctive information in the context of disjunctive databases as there is an interesting interplay between these two types of information. Extended generalized disjunctive paraconsistent relation is introduced as the main structure in this model. The relational algebra is appropriately generalized to work on extended generalized disjunctive paraconsistent relations and their correctness is established.


title: Paraconsistent Intuitionistic Fuzzy Relational Data Model

abstract: In this paper, we present a generalization of the relational data model based on paraconsistent intuitionistic fuzzy sets. Our data model is capable of manipulating incomplete as well as inconsistent information. Fuzzy relation or intuitionistic fuzzy relation can only handle incomplete information. Associated with each relation are two membership functions one is called truth-membership function $T$ which keeps track of the extent to which we believe the tuple is in the relation, another is called false-membership function which keeps track of the extent to which we believe that it is not in the relation. A paraconsistent intuitionistic fuzzy relation is inconsistent if there exists one tuple $a$ such that $T(a) + F(a) > 1$. In order to handle inconsistent situation, we propose an operator called split to transform inconsistent paraconsistent intuitionistic fuzzy relations into pseudo-consistent paraconsistent intuitionistic fuzzy relations and do the set-theoretic and relation-theoretic operations on them and finally use another operator called combine to transform the result back to paraconsistent intuitionistic fuzzy relation. For this model, we define algebraic operators that are generalisations of the usual operators such as union, selection, join on fuzzy relations. Our data model can underlie any database and knowledge-base management system that deals with incomplete and inconsistent information.


title: Mathematical knowledge management is needed

abstract: In this lecture I discuss some aspects of MKM, Mathematical Knowledge Management, with particuar emphasis on information storage and information retrieval.


title: Interval Neutrosophic Logics: Theory and Applications

abstract: In this paper, we present the interval neutrosophic logics which generalizes the fuzzy logic, paraconsistent logic, intuitionistic fuzzy logic and many other non-classical and non-standard logics. We will give the formal definition of interval neutrosophic propositional calculus and interval neutrosophic predicate calculus. Then we give one application of interval neutrosophic logics to do approximate reasoning.


title: Generalized Counters and Reversal Complexity

abstract: We generalize the definition of a counter and counter reversal complexity and investigate the power of generalized deterministic counter automata in terms of language recognition.


title: Robust Dialogue Understanding in HERALD

abstract: We tackle the problem of robust dialogue processing from the perspective of language engineering. We propose an agent-oriented architecture that allows us a flexible way of composing robust processors. Our approach is based on Shoham's Agent Oriented Programming (AOP) paradigm. We will show how the AOP agent model can be enriched with special features and components that allow us to deal with classical problems of dialogue understanding.


title: A knowledge-based approach to semi-automatic annotation of multimedia documents via user adaptation

abstract: Current approaches to the annotation process focus on annotation schemas, languages for annotation, or are very application driven. In this paper it is proposed that a more flexible architecture for annotation requires a knowledge component to allow for flexible search and navigation of the annotated material. In particular, it is claimed that a general approach must take into account the needs, competencies, and goals of the producers, annotators, and consumers of the annotated material. We propose that a user-model based approach is, therefore, necessary.


title: Semantic filtering by inference on domain knowledge in spoken dialogue systems

abstract: General natural dialogue processing requires large amounts of domain knowledge as well as linguistic knowledge in order to ensure acceptable coverage and understanding. There are several ways of integrating lexical resources (e.g. dictionaries, thesauri) and knowledge bases or ontologies at different levels of dialogue processing. We concentrate in this paper on how to exploit domain knowledge for filtering interpretation hypotheses generated by a robust semantic parser. We use domain knowledge to semantically constrain the hypothesis space. Moreover, adding an inference mechanism allows us to complete the interpretation when information is not explicitly available. Further, we discuss briefly how this can be generalized towards a predictive natural interactive system.


title: An argumentative annotation schema for meeting discussions

abstract: In this article, we are interested in the annotation of transcriptions of human-human dialogue taken from meeting records. We first propose a meeting content model where conversational acts are interpreted with respect to their argumentative force and their role in building the argumentative structure of the meeting discussion. Argumentation in dialogue describes the way participants take part in the discussion and argue their standpoints. Then, we propose an annotation scheme based on such an argumentative dialogue model as well as the evaluation of its adequacy. The obtained higher-level semantic annotations are exploited in the conceptual indexing of the information contained in meeting discussions.


title: Automatic Keyword Extraction from Spoken Text. A Comparison of two Lexical Resources: the EDR and WordNet

abstract: Lexical resources such as WordNet and the EDR electronic dictionary have been used in several NLP tasks. Probably, partly due to the fact that the EDR is not freely available, WordNet has been used far more often than the EDR. We have used both resources on the same task in order to make a comparison possible. The task is automatic assignment of keywords to multi-party dialogue episodes (i.e. thematically coherent stretches of spoken text). We show that the use of lexical resources in such a task results in slightly higher performances than the use of a purely statistically based method.