Search

In this paper, the parallel machine scheduling problem with DeJong's learning effect, is addressed. The objective function to be minimized is the makespan. This problem is proofed to be NP-Hard in the strong sense. This is the challenging theoretical side of the studied problem. Furthermore, several real-life situations in manufacturing and computer science are modeled using the current problem. Several algorithms intended to solve the studied problem within a reasonable computing time are proposed in literature. Among these algorithms the exact methods, which failed to solve the studied problem to optimality even for small size instances. In this paper several new heuristics and meta-heuristics are proposed. These heuristics are classified into three types. The first type is based on Longest Processing Time (LPT) rule. The innovation is the modification of the LPT rule in a way to cope efficiently with the learning effect concept, by randomizing the selection of the next scheduled job. The second type of heuristics, is taking advantage of an exact Branch and Bound algorithm, developed originally for the classical parallel machine scheduling problem. The contribution for this kind of heuristics is lying in the modification of the processing time values, according to a prefixed selected functions. The third type of methods is based in an adaptation of the Genetic Algorithm to the learning effect concept. This adaptation consists in enlarging the area of selection of the parameters values. To assess the performance and the efficiency of the proposed heuristics, a newly developed lower bound is proposed. This lower bound is based on a relaxation of the studied problem, which allows to obtain a minimum cost flow problem. Finally, an extensive experimental study is conducted over a benchmark test problems. The obtained results provide strong evidence that the proposed procedures outperform the earlier existing ones. • Modeling the learning effect in parallel machine scheduling problem. • Development of dispatching rules based heuristics. • Development of heuristics based on the resolution of NP-Hard problems. • Development of new tight lower bounds based on the maximum allowed position. • Caring out an extensive experimental study that confirms the efficiency of the proposed procedures. [ABSTRACT FROM AUTHOR]

The frequent detection of persistent per- and polyfluoroalkyl substances (PFAS) in organisms and environment coupled with surging evidence for potential detrimental impacts, have attracted widespread attention throughout the world. In order to reveal research hotspots and trends of technologies for PFAS removal, herein, we performed a data-driven analysis of 3975 papers and 436 patents from Web of Science Core Collection and Derwent Innovation Index databases up to 2023. The results showed that China and the USA led the way in the research of PFAS removal with outstanding contributions to publications. The progression generally transitioned from accidental discovery of decomposition, to experimentation with removal effects and mechanisms of existing methods, and finally to enhanced defluorination and mechanism-driven design approaches. The keywords co-occurrence network and technology classification together revealed the main knowledge framework, which was constructed and correlated through contaminants, substrates, materials, processes and properties. Moreover, adsorption was demonstrated to be the dominant removal process among the current studies. Subsequently, we concluded the principles, advances and drawbacks of enrichment and separation, biological methods, advanced oxidation and reduction processes. Further exploration indicated the hotspots such as alternatives and precursors for PFAS ("genx": 1.258, "f-53b": 0.337), degradable mineralization technologies ("photocatalytic degrad": 0.529, "hydrated electron": 0.374), environment-friendly remediation technologies ("phytoremedi": 0.939, "constructed wetland": 0.462) and combination with novel materials ("metal-organic framework": 1.115, "layered double hydroxid": 0.559) as well as computer science ("molecular dynamics simul": 0.559, "machine learn"). Furthermore, the future direction of technological innovation might lie in high-performance processes that minimize secondary pollution, the development of recyclable and renewable treatment agents, and collaborative control strategies for multiple pollutants. Overall, this study offers comprehensive and objective review for researchers and industry professionals in this field, enabling rapid access to knowledge guidance and insights into research frontiers. [Display omitted] [ABSTRACT FROM AUTHOR]

Polynomial reduction is one of the main tools in computational algebra with innumerable applications in many areas, both pure and applied. Since many years both the theory and an efficient design of the related algorithm have been solidly established. This paper presents a definition of the generic concept of polynomial reduction structure, studies its features and highlights the aspects needed in order to grant and to efficiently test the main properties (Noetherianity, confluence, ideal membership). The most significant aspect of this analysis is a negative reappraisal of the role of the notion of term ordering which is usually considered a central and crucial tool in the theory. In fact, as it was already established in the computer science context in relation with termination of algorithms, most of the properties can be obtained simply considering a well founded order, while the classical requirement that it be preserved by multiplication is irrelevant. The last part of the paper shows how the polynomial basis concepts present in literature are interpreted in our language and their properties are consequences of the general results established in the first part of the paper. [ABSTRACT FROM AUTHOR]

• Heterogeneous parallel computing is rarely taught in required undergraduate courses. • Concepts of heterogeneous computing can be taught even in CS1 and CS2. • Pollack's Rule and Amdahl's Law help motivate the shift to heterogeneous processors. • Using ARM processors, an instructor can show a low-power mode and SIMD operations. Heterogeneous architectures have emerged as a dominant platform, not only in high-performance computing but also in mobile processing, cloud computing, and the Internet of Things (IoTs). Because the undergraduate computer science curriculum includes so many topics, adding a new course as a required part of the curriculum without increasing the number of hours to graduation is difficult. Integration of heterogeneous computing requires a module-driven approach in which coverage of the topics is broken down into smaller units and dispersed throughout the curriculum. The module-driven approach has been successfully implemented in introducing parallel and distributed computing concepts. In this paper, we present a set of four teaching modules that introduce fundamental concepts in heterogeneous computing in lower-division computer science courses. The goal of these modules is not to teach students how to program heterogeneous systems but rather to expose them to this emerging trend and prepare them for material in future classes. Although concepts are covered at a high level, the modules emphasize active learning and include lab assignments that provide students with hands-on experience. We also present initial evaluation results for two of these modules based on their use in undergraduate courses at Texas State University. The results are quite encouraging both in terms of learning outcomes and student engagement and interest. [ABSTRACT FROM AUTHOR]

High Performance Computing (HPC) is a highly demanded discipline in companies and institutions. However, as students and also afterwards as professors, we observed a lack of HPC related content in the engineering degrees at our university, including Computer Science. Thus, we designed and offered the engineering students a non-mandatory course entitled "Build your own cluster employing Raspberry Pi" to provide the students with HPC skills. With this course, we covered the basics of supercomputing (hardware, networking, software tools, performance evaluation, cluster management, etc.). This was possible thanks to leveraging the flexibility and versatility of Raspberry Pi devices, and the students' motivation that arose from the hands-on experience. Moreover, the course included a "Teaching on demand" component to let the attendees choose a field to explore, based on their own interests. In this paper, we offer all the details to let anyone fully reproduce the course. Besides, we analyze and evaluate the methodology that let us fulfill our objectives: increase the students' HPC skills and knowledge in such a way that they feel capable of utilizing it in their mid-term professional career. • On-demand teaching helps in the adaption to the students' learning pace. • Compacting learning hours increases the contents to be covered in a hands-on course. • Raspberry Pi devices help to raise students' motivation. • Human resources are essential for successful on-demand teaching. • Get started in HPC can be done with reasonable hardware costs. [ABSTRACT FROM AUTHOR]

This paper studies the mathematical properties of collectively canalizing Boolean functions, a class of functions that has arisen from applications in systems biology. Boolean networks are an increasingly popular modeling framework for regulatory networks, and the class of functions studied here captures a key feature of biological network dynamics, namely that a subset of one or more variables, under certain conditions, can dominate the value of a Boolean function, to the exclusion of all others. These functions have rich mathematical properties to be explored. The paper shows how the number and type of such sets influence a function's behavior and define a new measure for the canalizing strength of any Boolean function. We further connect the concept of collective canalization with the well-studied concept of the average sensitivity of a Boolean function. The relationship between Boolean functions and the dynamics of the networks they form is important in a wide range of applications beyond biology, such as computer science, and has been studied with statistical and simulation-based methods. But the rich relationship between structure and dynamics remains largely unexplored, and this paper is intended as a contribution to its mathematical foundation. [ABSTRACT FROM AUTHOR]

Ada Lovelace is widely regarded as an early pioneer of computer science, due to an 1843 paper about Charles Babbage's Analytical Engine, which, had it been built, would have been a general-purpose computer. However, there has been considerable disagreement among scholars as to her mathematical proficiency. This paper presents the first account by historians of mathematics of the correspondence between Lovelace and the mathematician Augustus De Morgan from 1840–41. Detailed contextual analysis allows us to present a corrected ordering of the archive material, countering previous claims of Lovelace's mathematical inadequacies, and presenting a more nuanced assessment of her abilities. [ABSTRACT FROM AUTHOR]

• We present a comprehensive scientometric analysis of IJHCS (1969–2018) and CHI (1982–2018). • We performed a geopolitical analysis and found a static landscape dominated by few countries. • Several countries show interest in them, but are unable to have a significant publishing presence. • We analysed the evolution of research topics over time by adopting the Computer Science Ontology. • We detected several research trends emerging in the last ten years. In this paper we focus on the International Journal of Human-Computer Studies (IJHCS) as a domain of analysis, to gain insights about its evolution in the past 50 years and what this evolution tells us about the research landscape associated with the journal. To this purpose we use techniques from the field of Science of Science and analyse the relevant scholarly data to identify a variety of phenomena, including significant geopolitical patterns, the key trends that emerge from a topic-centric analysis, and the insights that can be drawn from an analysis of citation data. Because the area of Human-Computer Interaction (HCI) has always been a central focus for IJHCS, we also include in the analysis the CHI conference, which is the premiere scientific venue in HCI. Analysing both venues provides more data points to our study and allows us to consider two alternative viewpoints on the evolution of HCI research. [ABSTRACT FROM AUTHOR]

In this paper, we formulate configurable cloud-based VoIP call allocation problem as a special case of dynamic multi-objective bin-packing. We consider voice quality influenced by CPU stress, cost contributed by the number of billing hours for Virtual Machines (VMs) provisioning, and calls placed on hold due to under-provisioning resources. We distinguish call allocation strategies by the type and amount of information used for allocation: knowledge-free, utilization-aware, rental-aware, and load-aware. We propose and study a variety of strategies with static and dynamic policies of VM provisioning. To study realistic scenarios, we consider startup delays for VM provisioning, and three configurable parameters: utilization threshold, rental threshold, and prediction interval. They can be configured and dynamically adapted to cope with different objective preferences, workloads, and cloud properties. We conduct comprehensive simulation on the real workload of the MIXvoip company and show that the proposed strategies outperform ones currently in-use. • We address concepts of simulation visualization as a pedagogical tool for supporting computer science undergraduates. • We demonstrate the practicability and benefits of the proposed approach on allocation of calls in Cloud VoIP model. • We discuss call allocation strategies with different types and amounts of information used for provision on cloud environments with configurable parameters. • We describe how simulation model enhance the decision making of VoIP providers respect to quality of service and cost of infrastructure. [ABSTRACT FROM AUTHOR]

In this paper, we consider the perfect demand matching problem (PDM) which combines aspects of the knapsack problem along with the b -matching problem. It is a generalization of the maximum weight matching problem which has been fundamental in the development of theory of computer science and operations research. This problem is NP-hard and there exists a constant ϵ > 0 such that the problem admits no 1 + ϵ -approximation algorithm, unless P=NP. Here, we investigate the performance of a distributed message passing algorithm called Max-sum belief propagation for computing the problem of finding the optimal perfect demand matching. As the main result, we demonstrate the rigorous theoretical analysis of the Max-sum BP algorithm for PDM , and establish that within pseudo-polynomial-time, our algorithm could converge to the optimal solution of PDM , provided that the optimal solution of its LP relaxation is unique and integral. Different from the techniques used in previous literature, our analysis is based on primal-dual complementary slackness conditions, and thus the number of iterations of the algorithm is independent of the structure of the given graph. Moreover, to the best of our knowledge, this is one of a very few instances where BP algorithm is proved correct for NP-hard problems. • The perfect demand matching problem (PDM) is NP-hard and MAXSNP-complete. • Demonstrate the rigorous theoretical analysis of Max-sum belief propagation for PDM. • The algorithm converges to the optimal solution of PDM within pseudo-polynomial time. • Our analysis is based on primal-dual complementary slackness conditions. [ABSTRACT FROM AUTHOR]

The Hasse–Weil bound is a deep result in mathematics and has found wide applications in mathematics, theoretical computer science, information theory etc. In general, the bound is tight and cannot be improved. However, for some special families of curves the bound could be improved substantially. In this paper, we focus on the Hasse–Weil bound for the curve defined by y p − y = f ( x ) over the finite field F q , where p is the characteristic of F q . In 1993, Moreno–Moreno [7] gave an improvement to the Hasse–Weil bound for this family of curves. Recently, Kaufman and Lovett [4, FOCS2011] showed that the Hasse–Weil bound can be improved for this family of curves with f ( x ) = g ( x ) + h ( x ) , where g ( x ) is a polynomial of degree ≪ q and h ( x ) is a sparse polynomial of arbitrary degree but bounded weight degree. The other recent improvement by Rojas-Leon and Wan [9, Math. Ann. 2011] shows that an extra p can be removed for this family of curves if p is very large compared with polynomial degree of f ( x ) and log p ⁡ q . In this paper, we focus on the most interesting case for applications, namely p = 2 . We show that the Hasse–Weil bound for this special family of curves can be improved if q = 2 n with odd n ⩾ 3 which is the same case where Serre [10] improved the Hasse–Weil bound. However, our improvement is greater than Serre's and Moreno–Morenao's improvements for this special family of curves. Furthermore, our improvement works for p = 2 compared with the requirement of large p by Rojas-Leon and Wan. In addition, our improvement finds interesting applications to character sums, cryptography and coding theory. The key idea behind is that this curve has the Hasse–Witt invariant 0 and we show that the Hasse–Weil bound can be improved for any curves with the Hasse–Witt invariant 0. The main tool used in our proof involves Newton polygon and some results in algebraic geometry. [ABSTRACT FROM AUTHOR]

The resultant theory plays a crucial role in computational algebra and algebraic geometry. The theory has two aspects: algebraic and geometric. In this paper, we focus on the algebraic aspect. One of the most important and well known algebraic properties of the resultant is that it is equal to the determinant of the Sylvester matrix. In 2008, Odagiri proved that a similar property holds over the tropical semiring if one replaces subtraction with addition. The tropical semiring belongs to a large family of algebraic structures called commutative idempotent semiring. In this paper, we prove that the same property (with subtraction replaced with addition) holds over an arbitrary commutative idempotent semiring. [ABSTRACT FROM AUTHOR]

The definition of a support for multi-attribute range queries is mandatory for highly distributed systems. Even if several solutions have been proposed in the last decade, most of them do not meet the requirements of recent platforms, like IoT or smart cities. The paper presents an approach that builds a multidimensional Voronoi graph by exploiting the attributes of the objects published by a node. Our solution overcomes the curse of dimensionality issue affecting Voronoi Tessellations in high dimensional spaces by defining a Voronoi hierarchy. The paper formally defines the structure, analysis the complexity of the operations and presents experimental results. [ABSTRACT FROM AUTHOR]

Cultural aspects such as values, beliefs, and behavioral patterns influence the way technology is understood and used, and the impact it may cause on the environment and on people. Although there is influential literature devoted to the subject of values and culture in Human–Computer Interaction, there is still a lack of principled and practical artifacts and methods to support researchers and practitioners in their activities. In this paper, we present a Value-oriented and Culturally Informed Approach (VCIA) to sensitize and support Computer Science and Engineering professionals in taking values and culture into consideration throughout the design of interactive systems. The approach is grounded on theoretical and methodological bases of Organizational Semiotics, Building Blocks of Culture, and Socially Aware Computing. VCIA offers a set of artifacts and methods articulated to support the design process in its different stages and activities: from the identification of stakeholders and their values, to the organization of requirements and the evaluation of the designed solution. In this paper, we present VCIA’s principles, artifacts, and illustrate its usefulness in bringing values into consideration, supporting a socially aware system design. [ABSTRACT FROM AUTHOR]

Modeling frameworks such as Probabilistic I/O Automata (PIOA) and Markov Decision Processes permit both probabilistic and nondeterministic choices. In order to use these frameworks to express claims about probabilities of events, one needs mechanisms for resolving nondeterministic choices. For PIOAs, nondeterministic choices have traditionally been resolved by schedulers that have perfect information about the past execution. However, these schedulers are too powerful for certain settings, such as cryptographic protocol analysis, where information must sometimes be hidden. In this paper, we propose a new, less powerful nondeterminism-resolution mechanism for PIOAs, consisting of tasks and local schedulers . Tasks are equivalence classes of system actions that are scheduled by oblivious, global task sequences. Local schedulers resolve nondeterminism within system components, based on local information only. The resulting task-PIOA framework yields simple notions of external behavior and implementation, a new kind of simulation relation that is sound for proving implementation, and supports simple compositionality results. [ABSTRACT FROM AUTHOR]

Best-first search can be regarded as anytime scheme for producing lower bounds on the optimal solution, a characteristic that is mostly overlooked. We explore this topic in the context of AND/OR best-first search, guided by the MBE heuristic, when solving graphical models. In that context, the impact of the secondary heuristic for subproblem ordering may be significant, especially in the anytime context. Indeed, our paper illustrates this, showing that a new concept of bucket errors can advise in providing effective subproblem orderings in AND/OR search for both exact and anytime solutions. [ABSTRACT FROM AUTHOR]

Abstract: The aim of this paper is to introduce the dual notion of interval conjugate implications, the interval coimplications, as interval representations of corresponding conjugate fuzzy coimplications. Using the canonical representation, this paper considers both the correctness and the optimality criteria, in order to provide interpretation for fuzzy coimplications as the non-truth degree of conditional rule in expert systems and study the action of interval automorphisms on such interval fuzzy connectives. It is proved that interval automorphisms acting on -dual interval coimplications preserve the main properties of interval implications discussed in the literature including the duality principle. Lastly, the action of interval automorphisms on interval classes of border, model and S-coimplications are considered, summarized in commutative diagrams. [Copyright &y& Elsevier]

In recent years, power consumption has become one of the hottest research trends in computer science and industry. Most of the reasons are related to the operational budget and the environmental issues. In this paper, we would like to propose an energy-efficient solution for orchestrating the resource in cloud computing. In nature, the proposed approach firstly predicts the resource utilization of the upcoming period based on the Gaussian process regression method. Subsequently, the convex optimization technique is engaged to compute an appropriate quantity of physical servers for each monitoring window. This quantity of interest is calculated to ensure that a minimum number of servers can still provide an acceptable quality of service. Finally, a corresponding migrating instruction is issued to stack the virtual machines and turn off the idle physical servers to achieve the objective of energy savings. In order to evaluate the proposed method, we conduct the experiments using synthetic data from 29-day period of Google traces and real workload from the Montage open-source toolkit. Through the evaluation, we show that the proposed approach can achieve a significant result in reducing the energy consumption as well as maintaining the system performance. [ABSTRACT FROM AUTHOR]

Pattern languages are a well-established class of languages, but very little is known about their closure properties. In the present paper we establish a large number of closure properties of the terminal-free pattern languages, and we characterise when the union of two terminal-free pattern languages is again a terminal-free pattern language. We demonstrate that the equivalent question for general pattern languages is characterised differently, and that it is linked to some of the most prominent open problems for pattern languages. We also provide fundamental insights into a well-known construction of E-pattern languages as unions of NE-pattern languages, and vice versa. [ABSTRACT FROM AUTHOR]

Abstract: The Data Grid provides massive aggregated computing resources and distributed storage space to deal with data-intensive applications. Due to the limitation of available resources in the grid as well as production of large volumes of data, efficient use of the Grid resources becomes an important challenge. Data replication is a key optimization technique for reducing access latency and managing large data by storing data in a wise manner. Effective scheduling in the Grid can reduce the amount of data transferred among nodes by submitting a job to a node where most of the requested data files are available. In this paper two strategies are proposed, first a novel job scheduling strategy called Weighted Scheduling Strategy (WSS) that uses hierarchical scheduling to reduce the search time for an appropriate computing node. It considers the number of jobs waiting in a queue, the location of the required data for the job and the computing capacity of the sites Second, a dynamic data replication strategy, called Enhanced Dynamic Hierarchical Replication (EDHR) that improves file access time. This strategy is an enhanced version of the Dynamic Hierarchical Replication strategy. It uses an economic model for file deletion when there is not enough space for the replica. The economic model is based on the future value of a data file. Best replica placement plays an important role for obtaining maximum benefit from replication as well as reducing storage cost and mean job execution time. So, it is considered in this paper. The proposed strategies are implemented by OptorSim, the European Data Grid simulator. Experiment results show that the proposed strategies achieve better performance by minimizing the data access time and avoiding unnecessary replication. [Copyright &y& Elsevier]

Abstract: Let be a univariate polynomial with real coefficients, . Subdivision algorithms based on algebraic techniques (e.g., Sturm or Descartes methods) are widely used for isolating the real roots of in a given interval. In this paper, we consider a simple subdivision algorithm whose primitives are purely numerical (e.g., function evaluation). The complexity of this algorithm is adaptive because the algorithm makes decisions based on local data. The complexity analysis of adaptive algorithms (and this algorithm in particular) is a new challenge for computer science. In this paper, we compute the size of the subdivision tree for the SqFreeEVAL algorithm. The SqFreeEVAL algorithm is an evaluation-based numerical algorithm which is well-known in several communities. The algorithm itself is simple, but prior attempts to compute its complexity have proven to be quite technical and have yielded sub-optimal results. Our main result is a simple bound on the size of the subdivision tree for the SqFreeEVAL algorithm on the benchmark problem of isolating all real roots of an integer polynomial of degree and whose coefficients can be written with at most bits. Our proof uses two amortization-based techniques: first, we use the algebraic amortization technique of the standard Mahler–Davenport root bounds to interpret the integral in terms of and . Second, we use a continuous amortization technique based on an integral to bound the size of the subdivision tree. This paper is the first to use the novel analysis technique of continuous amortization to derive state of the art complexity bounds. [Copyright &y& Elsevier]

Abstract: We review in this paper some recent yet fundamental results on evaluating queries over probabilistic databases. While one can see this problem as a special instance of general purpose probabilistic inference, we describe in this paper two key database specific techniques that significantly reduce the complexity of query evaluation on probabilistic databases. The first is the separation of the query and the data: we show here that by doing so, one can identify queries whose data complexity is #P-hard, and queries whose data complexity is in PTIME. The second is the aggressive use of previously computed query results (materialized views): in particular, by rewriting a query in terms of views, one can reduce its complexity from #P-complete to PTIME. We describe a notion of a partial representation for views, and show that, once computed and stored, this partial representation can be used to answer subsequent queries on the probabilistic databases. evaluation. [Copyright &y& Elsevier]

Abstract: In this paper, we define and analyze the nowhere dense classes of graphs. This notion is a common generalization of proper minor closed classes, classes of graphs with bounded degree, locally planar graphs, classes with bounded expansion, to name just a few classes which are studied extensively in combinatorial and computer science contexts. In this paper, we show that this concept leads to a classification of general classes of graphs and to the dichotomy between nowhere dense and somewhere dense classes. This classification is surprisingly stable as it can be expressed in terms of the most commonly used basic combinatorial parameters, such as the independence number , the clique number , and the chromatic number . The remarkable stability of this notion and its robustness has a number of applications to mathematical logic, complexity of algorithms, and combinatorics. We also express the nowhere dense versus somewhere dense dichotomy in terms of edge densities as a trichotomy theorem. [Copyright &y& Elsevier]

Abstract: In recent years, an increasing number of Mixed Reality (MR) applications have been developed using agent technology — both for the underlying software and as an interface metaphor. However, no unifying field or theory currently exists that can act as a common frame of reference for these varied works. As a result, much duplication of research is evidenced in the literature. This paper seeks to fill this important gap by outlining “for the first time” a formal field of research that has hitherto gone unacknowledged, namely the field of Mixed Reality Agents (MiRAs), which are defined as agents embodied in a Mixed Reality environment. Based on this definition, a taxonomy is offered that classifies MiRAs along three axes: agency, based on the weak and strong notions outlined by ; corporeal presence, which describes the degree of virtual or physical representation (body) of a MiRA; and interactive capacity, which characterises its ability to sense and act on the virtual and physical environment. Furthermore, this paper offers the first comprehensive survey of the state-of-the-art of MiRA research and places each project within the proposed taxonomy. Finally, common trends and future directions for MiRA research are discussed. By defining Mixed Reality Agents as a formal field, establishing a common taxonomy, and retrospectively placing existing MiRA projects within it, future researchers can effectively position their research within this landscape, thereby avoiding duplication and fostering reuse and interoperability. [Copyright &y& Elsevier]

Abstract: Reliable transmission is a key issue for distributed real-time applications. The concept of Real-time Dependable Channel was introduced to provide availability to real-time transmission. Two aspects are important for the efficiency of a Real-time dependable channel: assuring the end-to-end delay bound and optimising the utilisation of network resources. A packet can miss its delay bound for two reasons: network congestion or network failure. The classic solution to this problem has been the use of Backup Channels which introduces the notion of availability at the expense of increasing the use of network resources. However, this over-provisioning of resources is potentially wasted, since the failure rate is very low. This paper introduces a new failure detection scheme for Real-time Transmission, which is called Proactive Backup Channel. This scheme is based on activating the backup channel before a network failure or congestion is produced. This way, the failure recovery time is reduced, and, as proven in the paper, the use of network resources is minimized. [Copyright &y& Elsevier]

Although speech derived from read texts, news broadcasts, and other similar prepared contexts can be recognized with high accuracy, recognition performance drastically decreases for spontaneous speech. This is due to the fact that spontaneous speech and read speech are significantly different acoustically as well as linguistically. This paper statistically and quantitatively analyzes differences in acoustic features between spontaneous and read speech using two large-scale speech corpora, “Corpus of Spontaneous Japanese (CSJ)” and “Japanese Newspaper Article Sentences (JNAS)”. Experimental results show that spontaneous speech can be characterized by reduced spectral space in comparison with that of read speech, and that the more spontaneous, the more the spectral space shrinks. This paper also clarifies that reduction in the spectral space leads to reduction in phoneme recognition accuracy. This result indicates that spectral reduction is one major reason for the decrease of recognition accuracy in spontaneous speech. [Copyright &y& Elsevier]

Abstract: This paper studies the problem of constructing a minimum-weight spanning tree (MST) in a distributed network. This is one of the most important problems in the area of distributed computing. There is a long line of gradually improving protocols for this problem, and the state of the art today is a protocol with running time due to Kutten and Peleg [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40–66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20–27], where denotes the diameter of the graph G. Peleg and Rubinovich [D. Peleg, V. Rubinovich, A near-tight lower bound on the time complexity of distributed MST construction, in: Proc. 40th IEEE Symp. on Foundations of Computer Science, 1999, pp. 253–261] have shown that time is required for constructing MST even on graphs of small diameter, and claimed that their result “establishes the asymptotic near-optimality” of the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40–66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20–27]. In this paper we refine this claim, and devise a protocol that constructs the MST in rounds, where is the MST-radius of the graph. The ratio between the diameter and the MST-radius may be as large as , and, consequently, on some inputs our protocol is faster than the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40–66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20–27] by a factor of . Also, on every input, the running time of our protocol is never greater than twice the running time of the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40–66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20–27]. As part of our protocol for constructing an MST, we develop a protocol for constructing neighborhood covers with a drastically improved running time. The latter result may be of independent interest. [Copyright &y& Elsevier]

Abstract: The ability to provide uniform shared-memory access to a significant number of processors in a single SMP node brings us much closer to the ideal PRAM parallel computer. Many PRAM algorithms can be adapted to SMPs with few modifications. Yet there are few studies that deal with the implementation and performance issues of running PRAM-style algorithms on SMPs. Our study in this paper focuses on implementing parallel spanning tree algorithms on SMPs. Spanning tree is an important problem in the sense that it is the building block for many other parallel graph algorithms and also because it is representative of a large class of irregular combinatorial problems that have simple and efficient sequential implementations and fast PRAM algorithms, but these irregular problems often have no known efficient parallel implementations. Experimental studies have been conducted on related problems (minimum spanning tree and connected components) using parallel computers, but only achieved reasonable speedup on regular graph topologies that can be implicitly partitioned with good locality features or on very dense graphs with limited numbers of vertices. In this paper we present a new randomized algorithm and implementation with superior performance that for the first time achieves parallel speedup on arbitrary graphs (both regular and irregular topologies) when compared with the best sequential implementation for finding a spanning tree. This new algorithm uses several techniques to give an expected running time that scales linearly with the number p of processors for suitably large inputs (). As the spanning tree problem is notoriously hard for any parallel implementation to achieve reasonable speedup, our study may shed new light on implementing PRAM algorithms for shared-memory parallel computers. The main results of this paper are [1.] A new and practical spanning tree algorithm for symmetric multiprocessors that exhibits parallel speedups on graphs with regular and irregular topologies; and [2.] an experimental study of parallel spanning tree algorithms that reveals the superior performance of our new approach compared with the previous algorithms. The source code for these algorithms is freely-available from our web site. [Copyright &y& Elsevier]

Computing the roots of a univariate polynomial is a fundamental and long-studied problem of computational algebra with applications in mathematics, engineering, computer science, and the natural sciences. For isolating as well as for approximating all complex roots, the best algorithm known is based on an almost optimal method for approximate polynomial factorization, introduced by Pan in 2002. Pan's factorization algorithm goes back to the splitting circle method from Schönhage in 1982. The main drawbacks of Pan's method are that it is quite involved 2 2 In Victor Pan's own words: “Our algorithms are quite involved, and their implementation would require a non-trivial work, incorporating numerous known implementation techniques and tricks”. In fact, we are not aware of any implementation of Pan's method. and that all roots have to be computed at the same time. For the important special case, where only the real roots have to be computed, much simpler methods are used in practice; however, they considerably lag behind Pan's method with respect to complexity. In this paper, we resolve this discrepancy by introducing a hybrid of the Descartes method and Newton iteration, denoted A New Dsc , which is simpler than Pan's method, but achieves a run-time comparable to it. Our algorithm computes isolating intervals for the real roots of any real square-free polynomial, given by an oracle that provides arbitrary good approximations of the polynomial's coefficients. A New Dsc can also be used to only isolate the roots in a given interval and to refine the isolating intervals to an arbitrary small size; it achieves near optimal complexity for the latter task. [ABSTRACT FROM AUTHOR]

In the committee coordination problem , a committee consists of a set of professors and committee meetings are synchronized, so that each professor participates in at most one committee meeting at a time. In this paper, we propose two snap-stabilizing distributed algorithms for the committee coordination. Snap-stabilization is a versatile property which requires a distributed algorithm to efficiently tolerate transient faults. Indeed, after a finite number of such faults, a snap-stabilizing algorithm immediately operates correctly, without any external intervention. We design snap-stabilizing committee coordination algorithms enriched with some desirable properties related to concurrency , (weak) fairness , and a stronger synchronization mechanism called 2- Phase Discussion . In our setting, all processes are identical and each process has a unique identifier. The existing work in the literature has shown that (1) in general, fairness cannot be achieved in committee coordination, and (2) it becomes feasible if each professor waits for meetings infinitely often. Nevertheless, we show that even under this latter assumption, it is impossible to implement a fair solution that allows maximal concurrency . Hence, we propose two orthogonal snap-stabilizing algorithms, each satisfying 2-phase discussion, and either maximal concurrency or fairness. The algorithm that implements fairness requires that every professor waits for meetings infinitely often. Moreover, for this algorithm, we introduce and evaluate a new efficiency criterion called the degree of fair concurrency . This criterion shows that even if it does not satisfy maximal concurrency, our snap-stabilizing fair algorithm still allows a high level of concurrency. [ABSTRACT FROM AUTHOR]

Trace monoids and heaps of pieces appear in various contexts in combinatorics. They also constitute a model used in computer science to describe the executions of asynchronous systems. The design of a natural probabilistic layer on top of the model has been a long standing challenge. The difficulty comes from the presence of commuting pieces and from the absence of a global clock. In this paper, we introduce and study the class of Bernoulli probability measures that we claim to be the simplest adequate probability measures on infinite traces. For this, we strongly rely on the theory of trace combinatorics with the Möbius polynomial in the key role. These new measures provide a theoretical foundation for the probabilistic study of concurrent systems. [ABSTRACT FROM AUTHOR]

An important question for Human–Computer Interaction is to understand the visual search strategies that people use to scan the results of a search engine and find the information relevant to their current task. Design proposals that support this task include space-filling thumbnails, faceted browsers, and textually enhanced thumbnails, amongst others. We argue that understanding the trade-offs in this space might be informed by a deep understanding of the visual search strategies that people choose given the constraints imposed by the natural ecology of images on the web, the human visual system, and the task demands. In the current paper we report, and empirically evaluate, a computational model of the strategies that people choose in response to these constraints. The model builds on previous insights concerning the human visual system and the adaptive nature of visual search. The results show that strategic parameters, including the number of features to look for, the evaluation-stopping rule, the gaze duration and the number of fixations are explained by the proposed computational model. [ABSTRACT FROM AUTHOR]

Full body gestures provide alternative input to video games that are more natural and intuitive. However, full-body game gestures designed by developers may not always be the most suitable gestures available. A key challenge in full-body game gestural interfaces lies in how to design gestures such that they accommodate the intensive, dynamic nature of video games, e.g., several gestures may need to be executed simultaneously using different body parts. This paper investigates suitable simultaneous full-body game gestures, with the aim of accommodating high interactivity during intense gameplay. Three user studies were conducted: first, to determine user preferences, a user-elicitation study was conducted where participants were asked to define gestures for common game actions/commands; second, to identify suitable and alternative body parts, participants were asked to rate the suitability of each body part (one and two hands, one and two legs, head, eyes, and torso) for common game actions/commands; third, to explore the consensus of suitable simultaneous gestures, we proposed a novel choice-based elicitation approach where participants were asked to mix and match gestures from a predefined list to produce their preferred simultaneous gestures. Our key findings include (i) user preferences of game gestures, (ii) a set of suitable and alternative body parts for common game actions/commands, (iii) a consensus set of simultaneous full-body game gestures that assist interaction in different interactive game situations, and (iv) generalized design guidelines for future full-body game interfaces. These results can assist designers and practitioners to develop more effective full-body game gestural interfaces or other highly interactive full-body gestural interfaces. [ABSTRACT FROM AUTHOR]

This paper deals with computability of interactive computations. It aims at the characterization and analysis of a general concept of interactive computation as a basis for the extension and generalization of the notion of computability to interactive computations. We extend the notion of computability to interactive computations. Instead of partial functions on natural numbers or on finite strings we work with functions and relations on infinite input and output streams. As part of the computability of such functions and relations on streams we treat the following aspects of interactive computations: • causality between input and output streams • realizability of single output streams for given input streams • the role of non-realizable output • relating non-realizable behaviors to state machines • the concept of interactive computation and computability for interactive systems • the role of time in computability. Finally, we relate our results to established notions of computability. [ABSTRACT FROM AUTHOR]

We investigate the diversity of participatory design research practice, based on a review of ten years of participatory design research published as full research papers at the Participatory Design Conferences (PDC) 2002–2012, and relate this body of research to five fundamental aspects of PD from classic participatory design literature. We identify five main categories of research contributions: Participatory Design in new domains , Participatory Design methods , Participatory Design and new technology , Theoretical contributions to Participatory Design , and Basic concepts in Participatory Design . Moreover, we identify how participation is defined, and how participation is conducted in experimental design cases, with a particular focus on interpretation, planning, and decision-making in the design process. [ABSTRACT FROM AUTHOR]

Abstract: The last 2 decades have seen a constantly increasing interest in mindfulness, due to its positive effects on health and well-being. Recently, a number of mobile applications aimed at supporting people in practicing mindfulness techniques have appeared, but their efficacy has not been formally evaluated yet. In this paper, we first introduce the reader to mindfulness techniques, traditional as well as computer-based. Then, we propose and evaluate a mobile application (called AEON) aimed at helping users in practicing thought distancing, i.e. a mindfulness technique that requires one not to react in response to his/her thoughts but to be aware of them and observe them while they go away. AEON allows the user to enter his/her thoughts and visualize them as written in ink on a parchment placed under water. By touching the screen, the user can interact with the water and produce waves that progressively dissolve each written thought. We evaluate AEON on a sample of naive meditators (i.e. people with no or minimal experience with meditation), contrasting it with two traditional thought distancing techniques that are not computer-based. The first traditional technique requires users to mentally visualize their thoughts as printed on clouds and observe them as they pass by, while the second requires users to write their thoughts on cards, then pick up the cards one at a time, look at them and toss them into a wastepaper basket. AEON obtained better results in terms of achieved mindfulness, perceived level of difficulty and degree of pleasantness. Since practicing mindfulness tends to be difficult for naive meditators, these results suggest that AEON can be a novel and effective way to help them approach mindfulness. [Copyright &y& Elsevier]

The displacement calculus of Morrill, Valentín and Fadda (2011) [25] aspires to replace the calculus of Lambek (1958) [13] as the foundation of categorial grammar by accommodating intercalation as well as concatenation while remaining free of structural rules and enjoying Cut-elimination and its good corollaries. Jäger (2005) [11] proposes a type logical treatment of anaphora with syntactic duplication using limited contraction. Morrill and Valentín (2010) [24] apply (modal) displacement calculus to anaphora with lexical duplication and propose extension with a negation as failure in conjunction with additives to capture binding conditions. In this paper we present an account of anaphora developing characteristics and employing machinery from both of these proposals. [ABSTRACT FROM AUTHOR]

Abstract: Privacy is a much discussed and politically charged topic in contemporary healthcare. Yet, studying the actual privacy practices of healthcare professionals and patients remains extremely challenging. In this paper we reflect on our experiences using qualitative methods in two projects on HIV care, the first researching internet use by a particular group of patients, and the second looking at issues of information technology integration in hospitals. Our aim in doing so is to highlight some of the opportunities and challenges involved in including an explicit focus on ‘context’ in qualitative privacy research in healthcare. We suggest that adopting a more reflexive approach to the way methods are used in relation to ‘context’ in privacy-related HCI research provides opportunities for understanding how different ‘privacy contexts’ are enacted in and through our research practices in different environments. [Copyright &y& Elsevier]

Abstract: This paper introduces Elastic Cloud Computing Cluster (EC3), a tool that creates elastic virtual clusters on top of Infrastructure as a Service (IaaS) Clouds. The clusters are self-managed entities that scale out to a larger number of nodes on demand, up to a maximum size specified by the user. Whenever idle resources are detected, the clusters automatically scale in, according to some predefined policies, in order to cut down the costs in the case of using a public Cloud provider. This creates the illusion of a real cluster without requiring an investment beyond the actual usage. Two different case studies are presented to assess the effectiveness of an elastic virtual cluster. The results show that the usage of self-managed elastic clusters represents an important economic saving when compared both to physical clusters and to static virtual clusters deployed on an IaaS Cloud, with a reduced penalty in the elasticity management. [Copyright &y& Elsevier]

Abstract: A t-interval is a union of at most t half-open intervals on the real line. An interval is the special case where . In this paper we study the problems of online selection of intervals and t-intervals. We derive lower bounds and (almost) matching upper bounds on the competitive ratios of randomized algorithms for selecting intervals, 2-intervals and t-intervals, for any . While offline t-interval selection has been studied before, the online version is considered here for the first time. [Copyright &y& Elsevier]

Abstract: The evaluation of interactive systems has been an active subject of research for many years. Many methods have been proposed, but most of them do not take the architectural specificities of an agent-based interactive system into account, nor do they focus on the link between architecture and evaluation. In this paper, we present an agent-based architecture model for interactive systems. Then, based on this architecture, we propose a generic, reconfigurable evaluation environment, called EISEval, designed and developed to help evaluators analyze and evaluate certain aspects of interactive systems in general and of agent-based architecture interactive systems in particular: User Interface (UI), non-functional properties (e.g., response time, complexity) and user characteristics (e.g., abilities, preferences, progress). System designers can draw useful conclusions from the evaluation results to improve the system. This environment was applied to evaluate an agent-based interactive system used to supervise an urban transport network in a study organized in laboratory. [Copyright &y& Elsevier]

Abstract: Modelling human tutors' socio-linguistic abilities computationally is necessary to underpin human–computer educational interactions with best pedagogic practices and to enhance the naturalness of such interactions. In this paper we present a computational model of tutorial feedback selection based on the context of the immediate situation for which the feedback is selected as well as on politeness considerations shown to be of importance to increasing pedagogical efficacy of computer assisted learning (Wang et al., 2008). The model is based on empirical studies with human tutors and on extensive linguistic analysis of human tutorial dialogues collected with the specific aim to inform the implementation of a natural language tutorial dialogue interface. The evaluation of the model, involving the comparison of its output with the linguistic responses produced by a human tutor, demonstrates the model's plausibility and highlights future directions for improving natural language human–computer interactions for educational purposes. [Copyright &y& Elsevier]

Abstract: Component-oriented programming has been applied to address the requirements of large-scale applications from computational sciences and engineering that present high performance computing (HPC) requirements. However, parallelism continues to be a challenging requirement in the design of CBHPC (Component-Based High Performance Computing) platforms. This paper presents strong evidence about the efficacy and the efficiency of HPE (Hash Programming Environment), a CBHPC platform that provides full support for parallel programming, on the development, deployment and execution of numerical simulation code onto cluster computing platforms. [Copyright &y& Elsevier]

Abstract: Secrecy is fundamental to computer security, but real systems often cannot avoid leaking some secret information. For this reason, it is useful to model secrecy quantitatively, thinking of it as a “resource” that may be gradually “consumed” by a system. In this paper, we explore this intuition through several dynamic and static models of secrecy consumption, ultimately focusing on (average) vulnerability and min-entropy leakage as especially useful models of secrecy consumption. We also consider several composition operators that allow smaller systems to be combined into a larger system, and explore the extent to which the secrecy consumption of a combined system is constrained by the secrecy consumption of its constituents. [Copyright &y& Elsevier]

Abstract: The cop-number of a graph is the minimum number of cops needed to catch a robber on the graph, where the cops and the robber alternate moving from a vertex to a neighbouring vertex. It is conjectured by Meyniel that for a graph on n vertices cops suffice. The aim of this paper is to investigate the cop-number of a random graph. We prove that for sparse random graphs the cop-number has order of magnitude . The best known strategy for general graphs is the area-defending strategy, where each cop ‘controls’ one region by himself. We show that, for general graphs, this strategy cannot be too effective: there are graphs that need at least cops for this strategy. [Copyright &y& Elsevier]

Abstract: The nature vs. nurture dualism has framed the modern conversation in biology and psychology. There is an analogous distinction for knowledge acquisition and artificial intelligence. In the context of building intelligent systems, nature means acquiring knowledge by being programmed or modeled that way. Nurture means acquiring knowledge by machine learning from data and information in the world. This paper develops the nature/nurture analogy in light of the history of knowledge acquisition, the current state of the art, and the future of intelligent machines learning from human knowledge. [Copyright &y& Elsevier]

Abstract: Knowledge-acquisition research started in the eighties as a small research community focusing on knowledge-intensive problems in relatively small domains. In this paper we look at the influence the Web has had on knowledge acquisition and vice versa. To this end we discuss in some depth four topics, namely the ontology language OWL, the vocabulary language SKOS, the notion of ontology alignment and the potential of semantic search. Even from this limited selection of research issues related to “Web knowledge” it is safe to conclude that the Web has had a large impact on knowledge acquisition, but also the other way around. [Copyright &y& Elsevier]

Abstract: In the early years of knowledge acquisition research there was considerable discussion about the possibility of obtaining knowledge from experts, based on the ideas of situated cognition. The central idea from situated cognition was that knowledge is only ever created in a context and so cannot be used reliably out of context. These ideas seem to have had little impact on most of the knowledge acquisition research that followed, probably because they seemed to be too negative about the possibilities for knowledge-based systems. This paper suggests that situated cognition can be reinterpreted as making the positive suggestion that if people distinguish between different conclusions in different contexts, they do so because they can identify features that distinguish the contexts. This type of case or context differentiation could be readily integrated with a range of knowledge acquisition frameworks, and experience with Ripple-Down Rules suggests that it provides a very simple way for domain experts and others to easily provide a large amount of knowledge for a system. [Copyright &y& Elsevier]

Abstract: In this paper, we study algebraic aggregate computations in Sensor Networks. The main contribution is the presentation of an early-stopping protocol that computes the average function under a harsh model of the conditions under which sensor nodes operate. This protocol is shown to be time-optimal in the presence of infrequent failures. The approach followed saves time and energy by the computation relying on a small network of delegate nodes that can be rebuilt fast in case of node failures and communicate using a collision-free schedule. Delegate nodes run two protocols simultaneously, namely, a collection/dissemination tree-based algorithm, which is shown to be optimal, and a mass-distribution algorithm. Both algorithms are analyzed under a model where the frequency of failures is a parameter. Other aggregate computation algorithms can be easily derived from this protocol. To the best of our knowledge, this is the first optimal early-stopping algorithm for aggregate computations in Sensor Networks. [Copyright &y& Elsevier]