SOFSEM 2001, the International conference on currenttrends in theory and practice of Informatics, was held on November 24 – December 1, 2001 in the ? well-known spa Pie?stany, Slovak Republic. this was the 28th annu...
详细信息
ISBN:
(数字)9783540456278
ISBN:
(纸本)9783540429128
SOFSEM 2001, the International conference on currenttrends in theory and practice of Informatics, was held on November 24 – December 1, 2001 in the ? well-known spa Pie?stany, Slovak Republic. this was the 28th annual conference in the SOFSEM series organized either in the Slovak or the Czech Republic. SOFSEM has a well-established tradition. currently it is a broad, multid- ciplinary conference, devoted to the theory and practice of software systems. Its aim is to foster cooperation among professionals from academia and industry working in various areas of informatics. the scienti?c program of SOFSEM consists of invited talks, which determine the topics of the conference, and short contributed talks presenting original - sults. the topics of the invited talks are chosen so as to cover the whole range from theory to practice and to bring interesting research areas to the attention of conference participants. For the year 2001, the following three directions were chosen for presentation by the SOFSEM Steering Committee: – trends in Informatics – Enabling Technologies for Global Computing – Practical Systems Engineering and Applications the above directions were covered through 12 invited talks presented by pro- nent researchers. there were 18 contributed talks, selected by the international Program Committee from among 46 submitted papers. the conference was also accompanied by workshops on Electronic Commerce Systems (coordinated by H. D. Zimmermann) and Soft Computing (coordinated by P. H´ajek).
Model complexity of feedforward neural networks is studied in terms of rates of variable-basis approximation. Sets of functions, for which the errors in approximation by neural networks with n hidden units converge to...
详细信息
A graph with forbidden transitions is a pair (G, F-G) where G := (V-G, E-G) is a graph and FG is a subset of the set {({y, x}, {x, z}) epsilon E-G(2)}. A path in a graph with forbidden transitions (G, F-G) is a path i...
详细信息
ISBN:
(纸本)9783642358432
A graph with forbidden transitions is a pair (G, F-G) where G := (V-G, E-G) is a graph and FG is a subset of the set {({y, x}, {x, z}) epsilon E-G(2)}. A path in a graph with forbidden transitions (G, F-G) is a path in G such that each pair ({y, x}, {x, z}) of consecutive edges does not belong to FG. It is shown in [S. Szeider, Finding paths in graphs avoiding forbidden transitions, DAM 126] that the problem of deciding the existence of a path between two vertices in a graph with forbidden transitions is Np-complete. We give an exact exponential time algorithm that decides in time O(2(n) center dot n(5) center dot log(n)) whether there exists a path between two vertices of a given n-vertex graph with forbidden transitions. We also investigate a natural extension of the minimum cut problem: we give a polynomial time algorithm that computes a set of forbidden transitions of minimum size that disconnects two given vertices (while in a minimum cut problem we are seeking for a minimum number of edges that disconnect the two vertices). the polynomial time algorithm for that second problem is obtained via a reduction to a standard minimum cut problem in an associated allowed line graph.
the mathematical analysis of robustness and error-tolerance of complex networks has been in the center of research interest. On the other hand, little work has been done when the attack-tolerance of the vertices or ed...
详细信息
ISBN:
(纸本)9783030108014;9783030108007
the mathematical analysis of robustness and error-tolerance of complex networks has been in the center of research interest. On the other hand, little work has been done when the attack-tolerance of the vertices or edges are not independent but certain classes of vertices or edges share a mutual vulnerability. In this study, we consider a graph and we assign colors to the vertices or edges, where the color-classes correspond to the shared vulnerabilities. An important problem is to find robustly connected vertex sets: nodes that remain connected to each other by paths providing any type of error (i.e. erasing any vertices or edges of the given color). this is also known as color-avoiding percolation. In this paper, we study various possible modeling approaches of shared vulnerabilities, we analyze the computational complexity of finding the robustly (color-avoiding) connected components. We find that the presented approaches differ significantly regarding their complexity.
this book contains the invited and contributed papers selected for presentation at SOFSEM 2021, the 47th International conference on currenttrends in theory and practice of computerscience, which was held online dur...
详细信息
ISBN:
(数字)9783030677312
ISBN:
(纸本)9783030677305
this book contains the invited and contributed papers selected for presentation at SOFSEM 2021, the 47th International conference on currenttrends in theory and practice of computerscience, which was held online during January 25–28, 2021, hosted by the Free University of Bozen-Bolzano, Italy.
A theory of one-tape linear-time Turing machines is quite different from its polynomial-time counterpart. this paper discusses the computational complexity of one-tape Turing machines of various machine types (determi...
详细信息
this book constitutes the refereed proceedings of the 40th International conference on currenttrends in theory and practice of computerscience, SOFSEM 2014, held in Nový Smokovec, Slovakia, in January 2014. the...
详细信息
ISBN:
(数字)9783319042985
ISBN:
(纸本)9783319042978
this book constitutes the refereed proceedings of the 40th International conference on currenttrends in theory and practice of computerscience, SOFSEM 2014, held in Nový Smokovec, Slovakia, in January 2014. the 40 revised full papers presented in this volume were carefully reviewed and selected from 104 submissions. the book also contains 6 invited talks. the contributions covers topics as: Foundations of computerscience, Software and Web Engineering, as well as Data, Information and Knowledge Engineering and Cryptography, Security and Verification.
We introduce restarting automata as two-way automata in order to obtain a more general model which is closer to our linguistic motivations. We study the notion of j-monotonicity to show the advantages of this model. W...
详细信息
this paper considers a game in which a single cop and a single robber take turns moving along the edges of a given graph G. If there exists a strategy for the cop which enables it to be positioned at the same vertex a...
详细信息
ISBN:
(纸本)9783030389192;9783030389185
this paper considers a game in which a single cop and a single robber take turns moving along the edges of a given graph G. If there exists a strategy for the cop which enables it to be positioned at the same vertex as the robber eventually, then G is called cop-win, and robber-win otherwise. In contrast to previous work, we study this classical combinatorial game on edge-periodic graphs. these are graphs with an infinite lifetime comprised of discrete time steps such that each edge e is assigned a bit pattern of length le, with a 1 in the i-th position of the pattern indicating the presence of edge e in the i-th step of each consecutive block of le steps. Utilising the known framework of reachability games, we obtain an O(LCM(L) . n(3)) time algorithm to decide if a given n-vertex edge-periodic graph Gt is cop-win or robber-win as well as compute a strategy for the winning player (here, L is the set of all edge pattern lengths le, and LCM(L) denotes the least common multiple of the set L). For the special case of edge-periodic cycles, we prove an upper bound of 2 . l . LCM(L) on the minimum length required of any edge-periodic cycle to ensure that it is robber-win, where l = 1 if LCM(L) = 2 . maxL, and l = 2 otherwise. Furthermore, we provide constructions of edge-periodic cycles that are cop-win and have length 1.5 . LCM(L) in the l = 1 case and length 3 . LCM(L) in the l = 2 case.
暂无评论