We present a characterization of the class of context-free trace languages in terms of cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are governed b...
详细信息
ISBN:
(纸本)9783642183805
We present a characterization of the class of context-free trace languages in terms of cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are governed by an external pushdown store.
Games are a classical model in the synthesis of controllers in the open setting. In particular, games of infinite length can represent systems which are not expected to reach a correct state, but rather to handle a co...
详细信息
ISBN:
(数字)9783540775669
ISBN:
(纸本)9783540775652
Games are a classical model in the synthesis of controllers in the open setting. In particular, games of infinite length can represent systems which are not expected to reach a correct state, but rather to handle a continuous stream of events. Yet, even longer sequences of events have to be considered when infinite sequences of events can occur in finite time - Zeno behaviours. In this paper, we extend two-player games to this setting by considering plays of ordinal length. Our two main results are determinacy of reachability games of length less than w(w) on finite arenas, and the PSPACE-completeness of deciding the winner in such a game.
the Target Set Selection problem takes as an input a graph G and a non-negative integer threshold thr(v) for every vertex v. A vertex v can get active as soon as at least thr(v) of its neighbors have been activated. T...
详细信息
ISBN:
(纸本)9783319731179;9783319731162
the Target Set Selection problem takes as an input a graph G and a non-negative integer threshold thr(v) for every vertex v. A vertex v can get active as soon as at least thr(v) of its neighbors have been activated. the objective is to select a smallest possible initial set of vertices, the target set, whose activation eventually leads to the activation of all vertices in the graph. We show that Target Set Selection is in FPT when parameterized withthe combined parameters clique-width of the graph and the maximum threshold value. this generalizes all previous FPT-membership results for the parameterization by maximum threshold, and thereby solves an open question from the literature. We stress that the time complexity of our algorithm is surprisingly well-behaved and grows only single-exponentially in the parameters.
In the last couple of decades, the popularity of neural networks has soared and they have been successfully utilized in many different domains across computerscience. However, their application in safety and security...
详细信息
ISBN:
(纸本)9798350342734
In the last couple of decades, the popularity of neural networks has soared and they have been successfully utilized in many different domains across computerscience. However, their application in safety and security-critical domains has been limited due to concerns regarding their reliability. Traditional methods for verifying neural networks (NNs) often uses linear Satisfiability Modulo theory (SMT) solvers. these solvers work well for simple and shallow NN architectures but face limitations regarding their inability to handle non-linear activations, pooling layers, and complex activation functions, commonly used in modern deep neural networks. In this paper, we explore the potential of non-linear SMT solvers to verify intricate neural network architectures. By leveraging non-linear SMT solvers, a wider range of activation functions can be considered, leading to more accurate reasoning about the behavior of complex deep neural networks. the focus is on using recent advancements in SMT solver development to verify NNs with non-linear activation functions, particularly in the context of computer Vision tasks. To test this idea, we conducted an experimental analysis to assess whether current non-linear SMT solvers can efficiently handle NNs with transcendent activation functions.
Motivated by a potentially flawed deployment of the. one time pad in a:recent quantum cryptographic application securing a bank transfer [1], we show how to implement a statistically secure system for message passing,...
详细信息
ISBN:
(纸本)354024302X
Motivated by a potentially flawed deployment of the. one time pad in a:recent quantum cryptographic application securing a bank transfer [1], we show how to implement a statistically secure system for message passing, that is, a channel with negligible failure rate secure against unbounded adversaries, using a one time pad based cryptosystem. We prove the security of our system in the framework put forward by Backes, Pfitzmann, and Waidner [2].
this book constitutes the conference proceedings of the 48th International conference on currenttrends in theory and practice of computerscience, SOFSEM 2023, held in Nový Smokovec, Slovakia, during January 15...
详细信息
ISBN:
(数字)9783031231018
ISBN:
(纸本)9783031231001
this book constitutes the conference proceedings of the 48th International conference on currenttrends in theory and practice of computerscience, SOFSEM 2023, held in Nový Smokovec, Slovakia, during January 15–18, 2023.;this workshop focuses on graphs problems and optimization; graph drawing and visualization; NP-hardness and fixed parameter tractability; communication and temporal graphs; complexity and learning; and robots and strings.
We investigate rational relations over trees. Our starting point is the definition of rational tree relations via rational expressions by Raoult (Bull. Belg. Math. Sec. 1997). We develop a new class of automata, calle...
详细信息
ISBN:
(数字)9783540775669
ISBN:
(纸本)9783540775652
We investigate rational relations over trees. Our starting point is the definition of rational tree relations via rational expressions by Raoult (Bull. Belg. Math. Sec. 1997). We develop a new class of automata, called asynchronous tree automata, which recognize exactly these relations. the automata theoretic approach is convenient for the solution of algorithmic problems (like the emptiness problem). the second contribution of this paper is a new subclass of the rational tree relations, called separate-rational tree relations, defined via a natural restriction on asynchronous tree automata. these relations are closed under composition, preserve regular tree languages, and generate precisely the regular sets in the unary case (all these properties fail for the general model), and they are still more powerful than, for instance, the automatic tree relations.
Unnaturally sounding speech prevents the listeners from recognizing the message of the signal. In this paper we demonstrate how a precise initial phase approximation can improve the naturalness of artificially generat...
详细信息
ISBN:
(数字)9783540361374
ISBN:
(纸本)354000145X
Unnaturally sounding speech prevents the listeners from recognizing the message of the signal. In this paper we demonstrate how a precise initial phase approximation can improve the naturalness of artificially generated speech. Using the Harmonic plus Noise Model provided by Stylianou as a framework for a Hungarian speech synthesis, the exact initial phase extension of the system can be easily performed. the proposed method turns out to be more effective in preserving the sound characteristics and quality than the original one.
the introduction into the field of software testing, automated software testing and diagnostics will be given together with explanation of fundamental terminology. the viewpoint of quality theory will be stressed. Pre...
详细信息
ISBN:
(纸本)3540413480
the introduction into the field of software testing, automated software testing and diagnostics will be given together with explanation of fundamental terminology. the viewpoint of quality theory will be stressed. Presented state of the art basic concepts of software testing, design of tests, their execution and methods of test evaluation will be selected according to their practical usage. the methodology will be demonstrated on case studies developed during practical software testing and diagnostics projects for large international companies in the field of industrial automation and medical instrumentation. the paper will be concluded with a summary of practical experience.
the k-COLORING problem is to test whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. If a graph C does not contain a graph H as an induced subgraph, then C ...
详细信息
ISBN:
(纸本)9783642276590;9783642276606
the k-COLORING problem is to test whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. If a graph C does not contain a graph H as an induced subgraph, then C is called H-free. For any fixed graph H on at most 6 vertices, it is known that 3-COLORING is polynomial-time solvable on H-free graphs whenever H is a linear forest and NP-complete otherwise. By solving the missing case P-2+P-3, we prove the same result for 4-COLORING provided that H is a fixed graph on at most 5 vertices.
暂无评论