326 research outputs found
Effect of GPa pressure on microstructures and heat transfer phenomena of aluminum alloys during solidification
No full text학위논문(박사) - 한국과학기술원 : 재료공학과, 1994.8, [ iv, 116 p. ]한국과학기술원 : 재료공학과
Do Bugs Propagate? An Empirical Analysis of Temporal Correlations Among Software Bugs
No full textThe occurrences of bugs are not isolated events, rather they may interact, affect each other, and trigger other latent bugs. Identifying and understanding bug correlations could help developers localize bug origins, predict potential bugs, and design better architectures of software artifacts to prevent bug affection. Many studies in the defect prediction and fault localization literature implied the dependence and interactions between multiple bugs, but few of them explicitly investigate the correlations of bugs across time steps and how bugs affect each other. In this paper, we perform social network analysis on the temporal correlations between bugs across time steps on software artifact ties, i.e., software graphs. Adopted from the correlation analysis methodology in social networks, we construct software graphs of three artifact ties such as function calls and type hierarchy and then perform longitudinal logistic regressions of time-lag bug correlations on these graphs. Our experiments on four open-source projects suggest that bugs can propagate as observed on certain artifact tie graphs. Based on our findings, we propose a hybrid artifact tie graph, a synthesis of a few well-known software graphs, that exhibits a higher degree of bug propagation. Our findings shed light on research for better bug prediction and localization models and help developers to perform maintenance actions to prevent consequential bugs
Simon’s Congruence Pattern Matching
No full textTesting Simon’s congruence asks whether two strings have the same set of subsequences of length no greater than a given integer. In the light of the recent discovery of an optimal linear algorithm for testing Simon’s congruence, we solve the Simon’s congruence pattern matching problem. The problem requires finding all substrings of a text that are congruent to a pattern under the Simon’s congruence. Our algorithm efficiently solves the problem in linear time in the length of the text by reusing results from previous computations with the help of new data structures called X-trees and Y-trees. Moreover, we define and solve variants of the Simon’s congruence pattern matching problem. They require finding the longest and shortest substring of the text as well as the shortest subsequence of the text which is congruent to the pattern under the Simon’s congruence. Two more variants which ask for the longest congruent subsequence of the text and optimizing the pattern matching problem are left as open problems
On the Linear Number of Matching Substrings
No full textWe study the number of matching substrings in the pattern matching problem. In general, there can be a quadratic number of matching substrings in the size of a given text. The linearizing restriction enables to find at most a linear number of matching substrings. We first explore two well-known linearizing restriction rules, the longest-match rule and the shortest-match substring search rule, and show that both rules give the same result when a pattern is an infix-free set even though they have different semantics. Then, we introduce a new linearizing restriction, the leftmost nonoverlapping match rule that is suitable for find-and-replace operations in text searching, and propose an efficient algorithm for the new rule when a pattern is described by a regular expression. We also examine the problem of obtaining the maximal number of non-overlapping matching substrings
Ranking binary unlabelled necklaces in polynomial time
No full textUnlabelled Necklaces are an equivalence class of cyclic words under both the rotation (cyclic shift) and the relabelling operations. The relabelling of a word is a bijective mapping from the alphabet to itself. The main result of the paper is the first polynomial-time algorithm for ranking unlabelled necklaces of a binary alphabet. The time-complexity of the algorithm is O(n6log 2n), where n is the length of the considered necklaces. The key part of the algorithm is to compute the rank of any word with respect to the set of unlabelled necklaces by finding three other ranks: the rank over all necklaces, the rank over symmetric unlabelled necklaces, and the rank over necklaces with an enclosing labelling. The last two concepts are introduced in this paper.</p
The degree of irreversibility in deterministic finite automata
No full textRecently, Holzer et al. gave a method to decide whether the language accepted by a given deterministic finite automaton (DFA) can also be accepted by some reversible deterministic finite automaton (REV-DFA), and eventually proved NL-completeness. Here, we show that the corresponding problem for nondeterministic finite state automata (NFA) is PSPACE-complete. The recent DFA method essentially works by minimizing the DFA and inspecting it for a forbidden pattern. We here study the degree of irreversibility for a regular language, the minimal number of such forbidden patterns necessary in any DFA accepting the language, and show that the degree induces a strict infinite hierarchy of languages. We examine how the degree of irreversibility behaves under the usual language operations union, intersection, complement, concatenation, and Kleene star, showing tight bounds (some asymptotically) on the degree.</p
THE GENERALIZATION OF GENERALIZED AUTOMATA: EXPRESSION AUTOMATA
No full textWe explore expression automata with respect to determinism and minimization. We define determinism of expression automata using prefix-freeness. This approach is, to some extent, similar to that of Giammarresi and Montalbano's definition of deterministic generalized automata. We prove that deterministic expression automata languages are a proper subfamily of the regular languages. We close by defining the minimization of deterministic expression automata
Nondeterministic state complexity of nested word automata
No full textAbstractWe study the nondeterministic state complexity of Boolean operations on regular languages of nested words. For union and intersection we obtain matching upper and lower bounds. For complementation of a nondeterministic nested word automaton with n states we establish a lower bound Ω(n!) that is significantly worse than the exponential lower bound for ordinary nondeterministic finite automata (NFA). We develop techniques to prove lower bounds for the size of nondeterministic nested word automata that extend the known techniques used for NFAs
The Generalization of Generalized Automata: Expression Automata
No full textWe explore expression automata with respect to determinism, minimization and primeness. We define determinism of expression automata using prefix-freeness. This approach is, to some extent, similar to that of Giammarresi and Montalbano's definition of deterministic generalized automata. We prove that deterministic expression automata languages are a proper subfamily of the regular languages. We define the minimization of deterministic expression automata. Lastly, we discuss prime prefix-free regular languages. Note that we have omitted almost all proofs in this preliminary version
- …
