A visual formalism called Visual Coordination Diagrams (VCD) for high-level design of heterogeneous systems is presented in this paper. the language is based on a state-transition operational semantics, which allows a...
详细信息
We consider the problem of matching reconfiguration, where we are given two matchings M-s and M-t in a graph G and the goal is to determine if there exists a sequence of matchings M-0, M-1,..., M-l, such that M-0 = M-...
详细信息
ISBN:
(数字)9783030108014
ISBN:
(纸本)9783030108014;9783030108007
We consider the problem of matching reconfiguration, where we are given two matchings M-s and M-t in a graph G and the goal is to determine if there exists a sequence of matchings M-0, M-1,..., M-l, such that M-0 = M-s, all consecutive matchings differ by exactly two edges (specifically, any matching is obtained from the previous one by the addition and deletion of one edge), and M-l = M-t. It is known that the existence of such a sequence can be determined in polynomial time [5]. We extend the study of reconfiguring matchings to account for the length of the reconfiguration sequence. We show that checking if we can reconfigure M-s to M-t in at most l steps is NP-hard, even when the graph is unweighted, bipartite, and the maximum degree is four, and the matchings M-s and M-t are maximum matchings. We propose two simple algorithmic approaches, one of which improves on the brute-force running time while the other is a SAT formulation that we expect will be useful in practice.
the value 1 problem is a natural decision problem in algorithmic game theory. For partially observable Markov decision processes with reachability objective, this problem is defined as follows: are there observational...
详细信息
ISBN:
(纸本)9783319042978;9783319042985
the value 1 problem is a natural decision problem in algorithmic game theory. For partially observable Markov decision processes with reachability objective, this problem is defined as follows: are there observational strategies that achieve the reachability objective with probability arbitrarily close to 1? this problem was shown undecidable recently. Our contribution is to introduce a class of partially observable Markov decision processes, namely #-acyclic partially observable Markov decision processes, for which the value 1 problem is decidable. Our algorithm is based on the construction of a two-player perfect information game, called the knowledge game, abstracting the behaviour of a #-acyclic partially observable Markov decision process M such that the first player has a winning strategy in the knowledge game if and only if the value of M is 1.
Incidents like the crash of Lion Air Flight 610 in 2018 challenge the design of reliable and secure cyber-physical systems that operate in the real-world and have to cope with unpredictable external phenomena and erro...
详细信息
ISBN:
(纸本)9783030677305;9783030677312
Incidents like the crash of Lion Air Flight 610 in 2018 challenge the design of reliable and secure cyber-physical systems that operate in the real-world and have to cope with unpredictable external phenomena and error-prone technology. We argue that their design needs to guarantee minimal machine consciousness, which expresses that these systems must operate with full awareness of (the state of) their components and the environment. the concept emerged from our recent effort to develop a computational model for conscious behavior in robots, based on the theory of automata. Making systems `minimal machine conscious' leads to more trustworthy systems, as it strengthens their behavioral flexibility in varying environments and their resilience to operation and cooperation failures of their components and as a whole. the notion of minimal machine consciousness has the potential to become one of the defining attributes of Industry 4.0.
the emergence of non-photorealistic rendering (NPR) over the greater part of a decade has created an intriguing new field espousing expression, abstraction and stylisation in preference to the traditional computer gra...
详细信息
ISBN:
(纸本)3905673592
the emergence of non-photorealistic rendering (NPR) over the greater part of a decade has created an intriguing new field espousing expression, abstraction and stylisation in preference to the traditional computer graphics concerns for photorealism. By lifting the burden of realism, NPR is capable of engaging with users, providing compelling and unique experiences through devices such as abstraction and stylisation. Many artistic and visual styles have been achieved by NPR including interactive and automated systems for drawing and painting. In this paper we outline the current state-of-the-art of NPR for visualisation and identify some current and future trends in NPR research.
Generating multimedia streams, such as in a netradio, is a task which is complex and difficult to adapt to every users' needs. We introduce a novel approach in order to achieve it, based on a dedicated high-level ...
详细信息
ISBN:
(纸本)9783642183805
Generating multimedia streams, such as in a netradio, is a task which is complex and difficult to adapt to every users' needs. We introduce a novel approach in order to achieve it, based on a dedicated high-level functional programming language, called Liquidsoap, for generating, manipulating and broadcasting multimedia streams. Unlike traditional approaches, which are based on configuration files or static graphical interfaces, it also allows the user to build complex and highly customized systems. this language is based on a model for streams and contains operators and constructions, which make it adapted to the generation of streams. the interpreter of the language also ensures many properties concerning the good execution of the stream generation.
the biggest challenge facing software developers today is how to gracefully evolve complex software systems in the face of changing requirements. We clearly need software systems to be more dynamic, compositional and ...
详细信息
ISBN:
(纸本)9783642112652
the biggest challenge facing software developers today is how to gracefully evolve complex software systems in the face of changing requirements. We clearly need software systems to be more dynamic, compositional and model-centric, but instead we continue to build systems that are static, baroque and inflexible. How can we better build change-enabled systems in the future? To answer this question, we propose to look back to one of the most successful systems to support change, namely Smalltalk. We briefly introduce Smalltalk with a few simple examples, and draw some lessons for software evolution. Smalltalk's simplicity, its reflective design, and its highly dynamic nature all go a long way towards enabling change in Smalltalk applications. We then illustrate how these lessons work in practice by reviewing a number of research projects that support software evolution by exploiting Smalltalk's design. We conclude by summarizing open issues and challenges for change-enabled systems of the future.
the proceedings contain 30 papers. the special focus in this conference is on currenttrends in theory and practice of Informatics. the topics include: the potential of grid, virtual laboratories and virtual organizat...
ISBN:
(纸本)9783540429128
the proceedings contain 30 papers. the special focus in this conference is on currenttrends in theory and practice of Informatics. the topics include: the potential of grid, virtual laboratories and virtual organizations for bio-sciences;agreement problems in fault-tolerant distributed systems;from feature maps to semantic landscapes;inference in rule-based systems by interpolation and extrapolation revisited;recent advances in wavelength routing;from metacomputing to grid computing: evolution or revolution;knowledge-based control systems;evolving interactive systems;distributed computations by autonomous mobile robots;formal verification methods for industrial hardware design;how can computerscience contribute to knowledge discovery;on the approximability of interactive knapsack problems;model checking communication protocols;pipelined decomposable BSP computers;quantum versus probabilistic one-way finite automata with counter;how to employ reverse search in distributed single source shortest paths;multi-agent systems as concurrent constraint processes;an order preserving scalable distributed data structure with constant access costs;approximative learning of regular languages;quantum finite state transducers;the reconstruction of polyominoes from approximately orthogonal projections;fast independent component analysis in kernel feature spaces;on majority voting games in trees;time and space complexity of reversible pebbling;two-way restarting automata and J-monotonicity;P-hardness of equivalence testing on finite-state processes and physical and economic aspects.
Many applications in sensor networks require positional information of the sensors. Recovering node positions is closely related to graph realization problems for geometric graphs. Here, we address the case where node...
详细信息
ISBN:
(纸本)9783540695066
Many applications in sensor networks require positional information of the sensors. Recovering node positions is closely related to graph realization problems for geometric graphs. Here, we address the case where nodes have angular information. Whereas Bruck et al. proved that the corresponding realization problem together with unit-disk-graph-constraints is NP-hard [2], we focus on rigid components which allow both efficient identification and fast, unique realizations. Our technique allows to identify maximum rigid components in graphs with partially known rigid components using a reduction to maximum flow problems. this approach is analyzed for the two-dimensional case, but can easily be extended to higher dimensions.
this book constitutes the proceedings of the 49th International conference on currenttrends in theory and practice of computerscience, SOFSEM 2024, held in Cochem, Germany, in February 2024.;the 33 full papers prese...
详细信息
ISBN:
(数字)9783031521133
ISBN:
(纸本)9783031521126
this book constitutes the proceedings of the 49th International conference on currenttrends in theory and practice of computerscience, SOFSEM 2024, held in Cochem, Germany, in February 2024.;the 33 full papers presented in this book were carefully reviewed and selected from 81 submissions. the book also contains one invited talk in full paper length.
暂无评论