On the correctness of electronic documents: studying,finding, and localizing inconsistency bugs in PDF readers and files

Electronic documents are widely used to store and share information such as bank statements, contracts, articles, maps and tax information. Many different applications exist for displaying a given electronic document, and users rightfully assume that documents will be rendered similarly independently of the application used. However, this is not always the case, and these inconsistencies, regardless of their causes—bugs in the application or the file itself—can become critical sources of miscommunication. In this paper, we present a study on the correctness of PDF documents and readers. We start by manually investigating a large number of real-world PDF documents to understand the frequency and characteristics of cross-reader inconsistencies, and find that such inconsistencies are common—13.5% PDF files are inconsistently rendered by at least one popular reader. We then propose an approach to detect and localize the source of such inconsistencies automatically. We evaluate our automatic approach on a large corpus of over 230 K documents using 11 popular readers and our experiments have detected 30 unique bugs in these readers and files. We also reported 33 bugs, some of which have already been confirmed or fixed by developers.     

Power and welfare in bargaining for coalition structure formation

We investigate a noncooperative bargaining game for partitioning n agents into non-overlapping coalitions. The game has n time periods during which the players are called according to an exogenous agenda to propose offers. With probability \(\delta \), the game ends during any time period \(t<n\). If it does, the first t players on the agenda get a chance to propose but the others do not. Thus, \(\delta \) is a measure of the degree of democracy within the game (ranging from democracy for \(\delta =0\), through increasing levels of authoritarianism as \(\delta \) approaches 1, to dictatorship for \(\delta =1\)). We determine the subgame perfect equilibrium (SPE) and study how a player’s position on the agenda affects his bargaining power. We analyze the relation between the distribution of power of individual players, the level of democracy, and the welfare efficiency of the game. We find that purely democratic games are welfare inefficient and that introducing a degree of authoritarianism into the game makes the distribution of power more equitable and also maximizes welfare. These results remain invariant under two types of player preferences: one where each player’s preference is a total order on the space of possible coalition structures and the other where each player either likes or dislikes a coalition structure. Finally, we show that the SPE partition may or may not be core stable.     

Heterotypic Scaffold Design Orchestrates Primary Cell Organization and Phenotypes in Cocultured Small Diameter Vascular Grafts

To facilitate true regeneration, a vascular graft should direct the evolution of a neovessel to obtain the function of a native vessel. For this, scaffolds have to permit the formation of an intraluminal endothelial cell monolayer, mimicking the tunica intima. In addition, when attempting to mimic a tunica media‐like outer layer, the stacking and orientation of vascular smooth muscle cells (vSMCs) should be recapitulated. An integral scaffold design that facilitates this has so far remained a challenge. A hybrid fabrication approach is introduced by combining solution electrospinning and melt electrowriting. This allows a tissue‐structure mimetic, hierarchically bilayered tubular scaffold, comprising an inner layer of randomly oriented dense fiber mesh and an outer layer of microfibers with controlled orientation. The scaffold supports the organization of a continuous luminal endothelial monolayer and oriented layers of vSM‐like cells in the media, thus facilitating control over specific and tissue‐mimetic cellular differentiation and support of the phenotypic morphology in the respective layers. Neither soluble factors nor a surface bioactivation of the scaffold is needed with this approach, demonstrating that heterotypic scaffold design can direct physiological tissue‐like cell organization and differentiation.     

Probabilistic Length-Reducing Two-Pushdown Automata

Hardness of a separation of nondeterminism, randomization and determinism for polynomial time computations has motivated the analysis of this issue for restricted models of computation. Following this line of research, we consider randomized length-reducing two-pushdown automata ( ), a natural extension of pushdown automata ( ). Our main results are as follows. We show that deterministic s are weaker than Las Vegas s which in turn are weaker than Monte Carlo s. Moreover, bounded two-sided error s are stronger than Monte Carlo s and they are able to recognize some languages which cannot be recognized nondeterministically. Finally, we prove that amplification is impossible for Las Vegas and Monte Carlo automata. Partially supported by MNiSW grant number N206 024 31/3826, 2006-2008. An extended abstract of this paper appeared in the MFCS06 Proceedings (Lecture Notes in Computer Science, vol. 4162, pp. 561–572, 2006).     

Using derivatives in time series classification

Over recent years the popularity of time series has soared. Given the widespread use of modern information technology, a large number of time series may be collected during business, medical or biological operations, for example. As a consequence there has been a dramatic increase in the amount of interest in querying and mining such data, which in turn has resulted in a large number of works introducing new methodologies for indexing, classification, clustering and approximation of time series. In particular, many new distance measures between time series have been introduced. In this paper, we propose a new distance function based on a derivative. In contrast to well-known measures from the literature, our approach considers the general shape of a time series rather than point-to-point function comparison. The new distance is used in classification with the nearest neighbor rule. In order to provide a comprehensive comparison, we conducted a set of experiments, testing effectiveness on 20 time series datasets from a wide variety of application domains. Our experiments show that our method provides a higher quality of classification on most of the examined datasets.     

Many-to-Many Communication in Radio Networks

Radio networks model wireless data communication when the bandwidth is limited to one wave frequency. The key restriction of such networks is mutual interference of packets arriving simultaneously at a node. The many-to-many (m2m) communication primitive involves p participant nodes from among n nodes in the network, where the distance between any pair of participants is at most d. The task is to have all the participants get to know all the input messages. We consider three cases of the m2m communication problem. In the ad-hoc case, each participant knows only its name and the values of n, p and d. In the partially centralized case, each participant knows the topology of the network and the values of p and d, but does not know the names of the other participants. In the centralized case, each participant knows the topology of the network and the names of all the participants. For the centralized m2m problem, we give deterministic protocols, for both undirected and directed networks, working in time, which is provably optimal. For the partially centralized m2m problem, we give a randomized protocol for undirected networks working in time with high probability (whp), and we show that any deterministic protocol requires time. For the ad-hoc m2m problem, we develop a randomized protocol for undirected networks that works in time whp. We show two lower bounds for the ad-hoc m2m problem. One lower bound states that any randomized protocol for the m2m ad hoc problem requires expected time. Another lower bound states that for any deterministic protocol for the m2m ad hoc problem, there is a network on which the protocol requires time when n−p(n)=Ω(n) and d>1, and that it requires Ω(n) time when n−p(n)=o(n). The results of this paper appeared in a preliminary form in “On many-to-many communication in packet radio networks” in Proceedings of the 10th Conference on Principles of Distributed Systems (OPODIS), Bordeaux, France, 2006, Lecture Notes in Computer Science 4305, Springer, Heidelberg, pp. 258–272. The work of B.S. Chlebus was supported by NSF Grant 0310503.     

A real‐time field experiment on search and rescue operations assisted by unmanned aerial vehicles

This paper reports on the performance of a novel system for supporting search and rescue activities, known as SARUAV (search and rescue unmanned aerial vehicle), in a field experiment during which a real‐world search scenario was simulated. The experiment took place on March 2–3, 2017, at two sites located in southwestern Poland. Three groups acted in the experiment: (1) SARUAV and unmanned aerial vehicle (UAV) operators, (2) ground searchers, and (3) participants who simulated being lost. In the uncomplicated topography without snow cover, the system identified the lost persons, and ground searchers found them 31 min after the SARUAV report had been disseminated. In the mountainous area covered with snow, one person was found within 9 min after searchers received the SARUAV report; however, the other two persons were not identified by SARUAV. The field experiment served as a proof of concept of the SARUAV system, confirmed its potential in person identification studies, and helped to identify numerous scientific and technical problems that need to be solved to develop a mature version of the system.     

Real-time hardware–software embedded vision system for ITS smart camera implemented in Zynq SoC

The article demonstrates the usefulness of heterogeneous System on Chip (SoC) devices in smart cameras used in intelligent transportation systems (ITS). In a compact, energy efficient system the following exemplary algorithms were implemented: vehicle queue length estimation, vehicle detection, vehicle counting and speed estimation (using multiple virtual detection lines), as well as vehicle type (local binary features and SVM classifier) and colour (k-means classifier and YCbCr colourspace analysis) recognition. The solution exploits the hardware–software architecture, i.e. the combination of reconfigurable resources and the efficient ARM processor. Most of the modules were implemented in hardware, using Verilog HDL, taking full advantage of the possible parallelization and pipeline, which allowed to obtain real-time image processing. The ARM processor is responsible for executing some parts of the algorithm, i.e. high-level image processing and analysis, as well as for communication with the external systems (e.g. traffic lights controllers). The demonstrated results indicate that modern SoC systems are a very interesting platform for advanced ITS systems and other advanced embedded image processing, analysis and recognition applications.