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.
During the last years, speed-up techniques for DIJKSTRA's algorithm have been developed that make the computation of shortest paths a matter of microseconds even oil huge road networks. the most sophisticated meth...
详细信息
ISBN:
(纸本)9783540958901
During the last years, speed-up techniques for DIJKSTRA's algorithm have been developed that make the computation of shortest paths a matter of microseconds even oil huge road networks. the most sophisticated methods enhance the graph by inserting shortcuts, i.e. additional edges, that represent shortest paths in the graph. Until now, all existing shortcut-insertion strategies are heuristics and no theoretical results on the topic are known. In this work, we formalize the problem of adding shortcuts as a graph augmentation problem, study the algorithmic complexity of the problem, give approximation algorithms and show how to stochastically evaluate a given shortcut assignment on graphs that are too big to evaluate it exactly.
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.
In this paper we provide several new results concerning word and matrix semigroup problems using counter automaton models. As a main result, we prove a new version of Post's correspondence problem to be undecidabl...
详细信息
ISBN:
(数字)9783540775669
ISBN:
(纸本)9783540775652
In this paper we provide several new results concerning word and matrix semigroup problems using counter automaton models. As a main result, we prove a new version of Post's correspondence problem to be undecidable and show its application to matrix semigroup problems, such as Any Diagonal Matrix Problem and Recurrent Matrix Problem. We also use infinite periodic traces in counter automaton models to show the undecidability of a new variation of the Infinite Post Correspondence Problem and Vector Ambiguity Problem for matrix semigroups.
the clique-chromatic number of a graph G = (V, E) denoted by chi(c)(G) is the smallest integer k such that there exists a partition of the vertex set of G into k subsets withthe property that no maximal clique of G i...
详细信息
ISBN:
(纸本)9783319042978;9783319042985
the clique-chromatic number of a graph G = (V, E) denoted by chi(c)(G) is the smallest integer k such that there exists a partition of the vertex set of G into k subsets withthe property that no maximal clique of G is contained in any of the subsets. Such a partition is called a k-clique-colouring of G. Recently Marx proved that deciding whether a graph admits a k-clique-colouring is Sigma(p)(2)-complete for every fixed k >= 2. Our main results are an O*(2(n)) time inclusion-exclusion algorithm to compute chi(c)(G) exactly, and a branching algorithm to decide whether a graph of bounded clique-size admits a 2-clique-colouring which runs in time O*(lambda(n)) for some lambda < 2.
the transitions of a stateless automaton do not depend on internal states but. solely on the symbols currently scanned by its heads accessing the input. or memory. We investigate stateless deterministic restarting aut...
详细信息
ISBN:
(纸本)9783540958901
the transitions of a stateless automaton do not depend on internal states but. solely on the symbols currently scanned by its heads accessing the input. or memory. We investigate stateless deterministic restarting automata that, after executing a rewrite step, Continue to read their tape before. performing a restart. Even the weakest class thus obtained contains the regular languages properly. the relations between different classes of stateless automata as well as between stateless automata and the corresponding types of automata with states are investigated, and it is shown that the language classes defined by the various types of deterministic stateless restarting automata without Auxiliary symbols are anti-AFLs that are not even closed under reversal.
the concept of situation proposed in Situ, a context-aware service-centric model, is the instant status of a software system environment, including context values and user's actions, as well as the predicated user...
详细信息
暂无评论