waashk/dblp huggingface dataset:
decomposing port automata. port automata are an operational model for component connectors in a coordination language such as reo. they describe which sets of ports can synchronize in each state of the connector being modelled. this paper presents decomposition theorems for port automata, namely that all (finite) port automata can be generated from a small set of primitive port automata. applying these results to component connectors means that all component connectors can be constructed from just two primitive connectors.
matraca: a tool to provide support for people with impaired vision when using the computer for simple tasks. this paper introduces a computational tool - matraca - developed for the purpose of minimizing accessibility constraints related to the use of computers by people with visual disabilities (low vision or blind users). matraca offers a text edition environment associated to a vocal spell checker and an interface with special graphical elements and sound elements manipulated by speech synthesizer and/or speech recognition. considering several aspects of accessibility, matraca provides several tasks that can be performed using the computer, where most of application are highly bounded to visual features, and dependence, considering the user profile. several quality technologies were included in matraca creating a flexible environment in an open source tool.
an intelligent video system for vehicle localization and tracking in police cars. this work aims at real-time in-car video analysis to detect several critical events in order to alarm and assist police action. particularly, detecting a tracked or stopped vehicle is a crucial task for further examination of suspects, protecting police safety, and remote monitoring from police station. this paper describes a comprehensive approach to localize targeted vehicles in the video under various environments and illumination conditions. the extracted geometry features on the moving objects and background are dynamically projected onto a 1d profile and are constantly tracked. we rely on temporal information of features for vehicle identification, which compensates for the complexity of vehicle shapes, colors and types. we investigated videos of day and night, and different types of roads, proving that our employed approach is robust and effective.
an adaptive block-set based management for large-scale flash memory. with rapid increase of the capacity of flash-memory storage systems, it becomes critical to provide efficient management for large-scale flash-memory. compared with ftl (flash translation layer), nftl (nand flash translation layer) provides less main-memory space requirements for large-scale flash memory. however, because each replacement block is exclusively used by a logical block, nftl exhibits poor space utilization of flash memory. in this paper, we present an adaptive block-set based flash memory management. the presented scheme adopts shared and exclusive replacement blocks, and allocates replacement blocks according to the update loads of logical blocks. the experimental results show that the presented scheme yields a better performance in garbage collection than nftl and fast (fully associative sector translation), keeping space utilization of flash memory at high level.
sosaa: a framework for integrating components & agents. modern computing systems require powerful software frameworks to ease their development and manage their complexity. these issues are addressed within both component-based software engineering and agent-oriented software engineering, although few integrated solutions exist. this paper discusses a novel integration strategy, which builds upon both paradigms to address their shortcomings while leveraging their different characteristics to define a complete software framework.
keeping diversity when exploring dynamic environments. this paper presents a new exploration mechanism based on a heterogeneous multi-agent system that combines attractive and repulsive agents. we provide experimental results about the performance of our mechanism in dynamic environments when resources continuously appear and disappear.
on-line adaptation of sequential mobile processes running concurrently. process management systems (pmss) are nowadays more and more used as a supporting tool for cooperative processes in pervasive and highly dynamic situations, such as emergency situations, pervasive healthcare or domotics/home automation. but in all such situations, designed processes can be easily invalidated since the execution environment may change continuously due to frequent unforeseeable events. in this work we deal with process adaptability, i.e., the ability of the pms to automatically cope with deviations, and we devise a sound and complete technique suitable for sequential processes running concurrently. the technique is based on a general framework which adopts the situation calculus, congolog and regression planning as basic elements. the applicability to the challenging scenario of emergency management is also shown.
remote software protection by orthogonal client replacement. in a typical client-server scenario, a trusted server provides valuable services to a client, which runs remotely on an untrusted platform. of the many security vulnerabilities that may arise (such as authentication and authorization), guaranteeing the integrity of the client code is one of the most difficult to address. this security vulnerability is an instance of the malicious host problem, where an adversary in control of the client's host environment tries to tamper with the client code. we propose a novel client replacement strategy to counter the malicious host problem. the client code is periodically replaced by new orthogonal clients, such that their combination with the server is functionally-equivalent to the original client-server application. the reverse engineering efforts of the adversary are deterred by the complexity of analysis of frequently changing, orthogonal program code. we use the underlying concepts of program obfuscation as a basis for formally defining and providing orthogonality. we also give preliminary empirical validation of the proposed approach.
concern-oriented business architecture engineering. organizations are subject to constant evolution and must systematically analyze and design the impact of change to implement it consistently across all organizational domains. a thorough understanding of all relevant business-related artifacts as well as their relationships is a prerequisite to achieve this. for many organizations, business architecture management is a means to ensure the correct and up-to-date documentation of these artifacts. one challenge of business architecture management is the development a company-specific business architecture meta model. two directions of existing work provide partial solutions: (1) generic (meta) modeling methods and (2) business architecture meta models and languages. we argue that these two approaches complement each other and should be applied in an integrated way. the goal of this contribution is to propose such an integrated approach to business architecture engineering. the development of this approach follows the design research process and is based on experiences gained in three industrial business architecture engineering projects.
discovering xml keys and foreign keys in queries. the xml has undoubtedly become a standard for data representation and manipulation. but most of xml documents are still created without the respective description of their structure, i.e. an xml schema. in this paper, we further enhance current methods for automatic inferring of an xml schema with discovering keys and foreign keys. we do not consider sample xml data for discovery but a set of queries in xquery and we show how constructs utilized in the queries can be used for the discovery.
open source vs. closed source software: towards measuring security. the increasing availability and deployment of open source software in personal and commercial environments makes open source software highly appealing for hackers, and others who are interested in exploiting software vulnerabilities. this deployment has resulted in a debate "full of religion" on the security of open source software compared to that of closed source software. however, beyond such arguments, only little quantitative analysis on this research issue has taken place. we discuss the state-of-the-art of the security debate and identify shortcomings. based on these, we propose new metrics, which allows to answer the question to what extent the review process of open source and closed source development has helped to fix vulnerabilities. we illustrate the application of some of these metrics in a case study on openoffice (open source software) vs. microsoft office (closed source software).
towards developing a trust-based security solution. wireless sensor network has emerged as a new information and data gathering paradigm based on the collaborative efforts of a large number of autonomous sensing devices. with small memories and processors, limited energy and tiny packets, sensor networks cannot afford traditional luxury security solutions; this limitation causes security threats. there are several important security challenges, including access control, message integrity and confidentiality, and trust solutions that require us to use a careful design of resource constraints for pursuing more enhanced security solutions for a wireless sensor network. in this paper, we present a new idea of persistent security solutions that support trust for general purpose wireless sensor networks.
routing and scheduling in multihop wireless networks with time-varying channels. we study routing and scheduling in multihop wireless networks. when data is transmitted from its source node to its destination node it may go through other wireless nodes as intermediate hops. the data transmission is node constrained, i.e. every node can transmit data to at most one neighboring node per time step. the transmission rates are time varying as a result of the changing wireless channel conditions.in this paper we assume that the data arrivals and transmission rates are governed by an adversary. the power of the adversary is limited by an admissibility condition which forbids the adversary from overloading any wireless node a priori. the node constrained transmission and the time-varying nature of the transmission rates make our model different from and harder than the standard adversarial queueing model which relates to wireline networks.for the case in which the adversary specifies the paths that the data must follow, we design scheduling algorithms that ensure network stability. these algorithms try to give priority to data that is closest to its source node. however, at each time step only a subset of the data queued at a node is eligible for scheduling. one of our algorithms is fully distributed.for the case in which the adversary does not dictate the data paths, we show how to route the data so that the admissibility condition is satisfied. we can then schedule data along the chosen paths using our stable scheduling algorithms. we conclude by discussing the performance of distributed load balancing algorithms for combined routing and scheduling.
weighted isotonic regression under the norm. isotonic regression, the problem of finding values that best fit given observations and conform to specific ordering constraints, has found many applications in biomedical research and other fields. when the constraints form a partial ordering, solving the problem under the l1 error measure takes o(n3) when there are n observations. the analysis of large-scale microarray data, which is one of the important tools in biology, using isotonic regression is hence expensive. this is because in microarray analysis, the same procedure is used for studying the fit of tens of thousands of genes to a given partial order. fast estimation for the fitting error is therefore highly desired to reduce the number of regression instances through pruning. in this paper, we present approximation algorithms to the isotonic regression problem under the l1 error measure. we relate the problem to an edge packing problem and in the special case when the observations are not weighted, we relate it to a weighted matching problem.
compact labeling schemes for ancestor queries. we consider the following problem. give a rooted tree t, label the nodes of t in the most compact way such that given the labels of two nodes one can determine in constant time, by looking only at the labels, if one node is an ancestor of the other. the best known labeling scheme is rather straightforward and uses labels of size at most 2 log n, where n is the number of vertices in the tree. our main result in this paper is a labeling scheme with maximum label size close to 3/2 log n. our motivation for studying this problem is enhancing the performance of web search engines. in the context of this application each indexed document is a tree and the labels of all trees are maintained in main memory. therefore even small improvements in the maximum label size are important. there are no lower bounds known for this problem except for an obvious lower bound of log n that follows from the fact that different vertices must have different labels. the question whether one can find even shorter labels remains an intriguing open question.
popular matchings. we consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a nonempty subset of posts in order of preference, possibly involving ties. we say that a matching $m$ is popular if there is no matching $m'$ such that the number of applicants preferring $m'$ to $m$ exceeds the number of applicants preferring $m$ to $m'$. in this paper, we give the first polynomial-time algorithms to determine if an instance admits a popular matching and to find a largest such matching, if one exists. for the special case in which every preference list is strictly ordered (i.e., contains no ties), we give an $o(n + m)$ time algorithm, where $n$ is the total number of applicants and posts and $m$ is the total length of all of the preference lists. for the general case in which preference lists may contain ties, we give an $o(\sqrt{n}m)$ time algorithm.
comparison-sorting and selecting in totally monotone matrices. an m x n matrix a is called totally monotone if for all i1 < i2 and j1 < j2, a[i1, j1] > a[i1, j2 implies a[i2, j1] > a[i2, j2]. we consider the complexity of comparison-based selection and sorting algorithms in such matrices. although our selection algorithm counts only comparisons its advantage on all previous work is that it can also handle selection of elements of different (and arbitrary) ranks in different rows (or even selection of elements of several ranks in each row), in time which is slightly better than that of the best known algorithm for selecting elements of the same rank in each row. we also determine the decision tree complexity of sorting each row of a totally monotone matrix up to a factor of at most log n by proving a quadratic lower bound and by slightly improving the upper bound. no nontrivial lower bound was previously known for this problem. in particular for the case m = n we prove a tight &ohgr;(n2) lower bound. this bound holds for any decision-tree algorithm, and not only for a comparison-based algorithm. the lower bound is proved by an exact characterization of the bitonic totally monotone matrices, whereas our new algorithms depend on techniques from parallel comparison algorithms.
revenue maximization when bidders have budgets. we study the problem of maximizing revenue for auctions with multiple units of a good where bidders have hard budget constraints, first considered in [2]. the revenue obtained by an auction is compared with the optimal omniscient auction had the auctioneer known the private information of all the bidders, as in competitive analysis [7]. we show that the revenue of the optimal omniscient auction that sells items at many different prices is within a factor of 2 of the optimal omniscient auction that sells all the items at a single price, implying that our results will carry over to multiple price auctions. we give the first auction for this problem, to the best of our knowledge, that is known to obtain a constant fraction of the optimal revenue when the bidder dominance (the ratio between the maximum contribution of a single bidder in the optimal solution and the revenue of that optimal solution) is large (as high as 1/2). our auction is also shown to remain truthful if canceled upon not meeting certain criteria. on the negative side, we show that no auction can achieve a guarantee of 1/2-&epsilon; the revenue of the optimal omniscient multi-price auction. finally, if the bidder dominance is known in advance and is less than 1/5.828, we give an auction mechanism that raises a large constant fraction of the optimal revenue when the bidder dominance is large and is asymptotically close to the optimal omniscient auction as the bidder dominance decreases. we discuss the relevance of these results for related applications.
a general approach to online network optimization problems. we study a wide range of online graph and network optimization problems, focusing on problems that arise in the study of connectivity and cuts in graphs. in a general online network design problem, we have a communication network known to the algorithm in advance. what is not known in advance are the bandwidth or cut demands between nodes in the network. our results include an o(log m log n) competitive randomized algorithm for the online non-metric facility location and for a generalization of the problem called themulticast problem. in the non-metric facility location m is the number of facilities and n is the number of clients. the competitive ratio is nearly tight. we also present ano(log2 n log k) competitive randomized algorithm for the on-line group steiner problem in trees and an o(log3 n log k)competitive randomized algorithm for the problem in general graphs, where n is the number of vertices in the graph and k is the number of groups. finally, we design a deterministic o(log3 n log log n) competitive algorithm for the online multi-cut problem. our algorithms are based on a unified framework for designing online algorithms for problems involving connectivity and cuts. we first present a general o(log m)-deterministic algorithm for generating fractional solution that satisfies the online connectivity or cut demands, where m is the number of edges in the graph.
dynamizing static algorithms, with applications to dynamic trees and history independence. we describe a machine model for automatically dynamizing static algorithms and apply it to history-independent data structures. static programs expressed in this model are dynamized automatically by keeping track of dependences between code and data in the form of a dynamic dependence graph. to study the performance of such automatically dynamized algorithms we present an analysis technique based on trace stability. as an example of the use of the model, we dynamize the parallel tree contraction algorithm of miller and reif to obtain a history-independent data structure for the dynamic trees problem of sleator and tarjan.
the set-associative cache performance of search trees. we consider the costs of access to data stored in search trees assuming that those memory accesses are managed with a cache. our cache memory model is two-level, has a small degree of set-associativity, and uses lru replacement, and we consider the number of cache misses that a set of accesses incurs. for standard tree access--searches and traversals---changing the degree of set-associativity has no effect on performance.to explain this, we develop general stochastic access models, an adaptation of the independent reference model (irm), and analyze the expected number of cache hits and misses incurred by these types of access. the models and analyses are accurate: we are able to exactly predict the cache performance of tree data structures. in addition, we prove why set-associativity is of little or no benefit for these types of memory access and give examples where direct-mapping performs better than set-associativity.
exponential bounds for dpll below the satisfiability threshold. for each k &le; 4, we give &tau;k > 0 such that a random k-cnf formula f with n variables and &lfloor;rkn&rfloor; clauses is satisfiable with high probability, but ordered-dll takes exponential time on f with uniformly positive probability. using results of [2], this can be strengthened to a high probability result for certain natural backtracking schemes and extended to many other dpll algorithms.
improved fast integer sorting in linear space. we present improved fast deterministic algorithm for integer sorting in linear space. our algorithm sorts n integers in linear space in &ogr;(n log log n log log log n) time. this improves the &ogr;(n(log log n)3/2) time bound given in [6]. when the n integers in {0,1,&hellip;, m - 1} to be sorted satisfying log m &gne;(log n)2+&isin;, 0 < &isin; < 1, the time complexity for sorting can be further reduced to &ogr;(n log log n). these results are obtained by applying signature sorting on our previous result[6].
on the number of rectangular partitions. how many ways can a rectangle be partitioned into smaller ones? we study two variants of this problem: when the partitions are constrained to lie on n given points (no two of which are corectilinear), and when there are no such constraints and all we require is that the number of (non-intersecting) segments is n. in the first case, when the order (permutation) of the points conforms with a certain property, the number of partitions is the (n + 1)st baxter number, b(n + 1); the number of permutations conforming with the property is the (n - 1)st schr&ouml;der number; and the number of guillotine partitions is the nth schr&ouml;der number. in the second case, it is known [22] that the number of partitions and the number of guillotine partitions correspond to the baxter and schr&ouml;der numbers, respectively. our contribution is a bijection between permutations and partitions. our results provide interesting and new geometric interpretations to both baxter and schr&ouml;der numbers and suggest insights regarding the intricacies of the interrelations.
ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics. we introduce a new notion of embedding, called minimum-relaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. in an ordinal embedding, it is the relative order between pairs of distances, and not the distances themselves, that must be preserved as much as possible. the (multiplicative) relaxation of an ordinal embedding is the maximum ratio between two distances whose relative order is inverted by the embedding. we develop several worst-case bounds and approximation algorithms on ordinal embedding. in particular, we establish that ordinal embedding has many qualitative differences from metric embedding, and we capture the ordinal behavior of ultrametrics and shortest-path metrics of unweighted trees.