Search results for "Computer Networks and Communication"
showing 10 items of 834 documents
First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
2005
A language L over an alphabet A is said to have a neutral letter if there is a letter [email protected]?A such that inserting or deleting e's from any word in A^* does not change its membership or non-membership in L. The presence of a neutral letter affects the definability of a language in first-order logic. It was conjectured that it renders all numerical predicates apart from the order predicate useless, i.e., that if a language L with a neutral letter is not definable in first-order logic with linear order, then it is not definable in first-order logic with any set N of numerical predicates. Named after the location of its first, flawed, proof this conjecture is called the Crane Beach …
Balls into non-uniform bins
2014
Balls-into-bins games for uniform bins are widely used to model randomized load balancing strategies. Recently, balls-into-bins games have been analysed under the assumption that the selection probabilities for bins are not uniformly distributed. These new models are motivated by properties of many peer-to-peer (P2P) networks, which are not able to perfectly balance the load over the bins. While previous evaluations try to find strategies for uniform bins under non-uniform bin selection probabilities, this paper investigates heterogeneous bins, where the "capacities" of the bins might differ significantly. We show that heterogeneous environments can even help to distribute the load more eve…
Randomized renaming in shared memory systems.
2021
Abstract Renaming is a task in distributed computing where n processes are assigned new names from a name space of size m . The problem is called tight if m = n , and loose if m > n . In recent years renaming came to the fore again and new algorithms were developed. For tight renaming in asynchronous shared memory systems, Alistarh et al. describe a construction based on the AKS network that assigns all names within O ( log n ) steps per process. They also show that, depending on the size of the name space, loose renaming can be done considerably faster. For m = ( 1 + ϵ ) ⋅ n and constant ϵ , they achieve a step complexity of O ( log log n ) . In this paper we consider tight as well as loos…
Estimating the length of minimal spanning trees in compression of files
1984
Compression of a formatted file by a minimal spanning tree (MST) is studied. Here the records of the file are considered as the nodes of a weighted undirected graph. Each record pair is connected in the graph and the corresponding arc is weighted by the sum of field lengths of those fields which differ in the two records. The actual compression is made by constructing an MST of the graph and by storing it in an economic way to preserve the information of the file. The length of the MST is a useful measure in the estimation of the power of the compression. In the paper we study upper bounds of this length, especially in the case where the field lengths of the different fields may vary. The u…
Building Semantic Trees from XML Documents
2016
International audience; The distributed nature of the Web, as a decentralized system exchanging information between heterogeneous sources, has underlined the need to manage interoperability, i.e., the ability to automatically interpret information in Web documents exchanged between different sources, necessary for efficient information management and search applications. In this context, XML was introduced as a data representation standard that simplifies the tasks of interoperation and integration among heterogeneous data sources, allowing to represent data in (semi-) structured documents consisting of hierarchically nested elements and atomic attributes. However, while XML was shown most …
A novel XML document structure comparison framework based-on sub-tree commonalities and label semantics
2012
International audience; XML similarity evaluation has become a central issue in the database and information communities, its applications ranging over document clustering, version control, data integration and ranked retrieval. Various algorithms for comparing hierarchically structured data, XML documents in particular, have been proposed in the literature. Most of them make use of techniques for finding the edit distance between tree structures, XML documents being commonly modeled as Ordered Labeled Trees. Yet, a thorough investigation of current approaches led us to identify several similarity aspects, i.e., sub-tree related structural and semantic similarities, which are not sufficient…
A Life Cycle Model of XML Documents
2014
Electronic documents produced in business processes are valuable information resources for organizations. In many cases they have to be accessible long after the life of the business processes or information systems in connection with which they were created. To improve the management and preservation of documents, organizations are deploying Extensible Markup Language (XML) as a standardized format for documents. The goal of this paper is to increase understanding of XML document management and provide a framework to enable the analysis and description of the management of XML documents throughout their life. We followed the design science approach. We introduce a document life cycle model…
Programming languages for data-Intensive HPC applications: A systematic mapping study
2020
This work is a result of activities from COST Action 10406 High -Performance Modelling and Simulation for Big Data Applications (cHiPSet), funded by the European Cooperation in Science and Technology. FCT, Portugal for grants: NOVA LINCS Research Laboratory Ref. UID/ CEC/ 04516/ 2019); INESC-ID Ref. UID/CEC/50021/2019; BioISI Ref. UID/MULTI/04046/2103; LASIGE Research Unit Ref. UID/CEC/00408/ 2019. A major challenge in modelling and simulation is the need to combine expertise in both software technologies and a given scientific domain. When High-Performance Computing (HPC) is required to solve a scientific problem, software development becomes a problematic issue. Considering the complexity…
A novel methodology for accelerating bitstream relocation in partially reconfigurable systems
2012
International audience; Xilinx Virtex FPGAs offer the possibility of Partial Reconfiguration (PR). Arbitrary tasks can be allocated and de-allocated onto FPGA without system interruption. However, mapping a task to any available PR region requires a unique partial bitstream for each partition, hence reducing memory storage requirements. In recent years, an interest on overcoming this problem has lead to the concept of Partial Bitstream Relocation (PBR). The principle is to perform bitstream modification to map it to different regions. However, PBR consumes scarce resources in hardware implementations, and introduces a prohibitive time overhead when done in software. In order to find the bes…
GAIML: A New Language for Verbal and Graphical Interaction in Chatbots
2008
Natural and intuitive interaction between users and complex systems is a crucial research topic in human-computer interaction. A major direction is the definition and implementation of systems with natural language understanding capabilities. The interaction in natural language is often performed by means of systems called chatbots. A chatbot is a conversational agent with a proper knowledge base able to interact with users. Chatbots appearance can be very sophisticated with 3D avatars and speech processing modules. However the interaction between the system and the user is only performed through textual areas for inputs and replies. An interaction able to add to natural language also graph…