DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2022.60

Simon’s Congruence Pattern Matching

Authors: Sungmin Kim, Sang-Ki Ko, and Yo-Sub Han

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract

Testing 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.

Cite as

Sungmin Kim, Sang-Ki Ko, and Yo-Sub Han. Simon’s Congruence Pattern Matching. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.ISAAC.2022.60,
  author =	{Kim, Sungmin and Ko, Sang-Ki and Han, Yo-Sub},
  title =	{{Simon’s Congruence Pattern Matching}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{60:1--60:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.60},
  URN =		{urn:nbn:de:0030-drops-173456},
  doi =		{10.4230/LIPIcs.ISAAC.2022.60},
  annote =	{Keywords: pattern matching, Simon’s congruence, string algorithm, data structure}
}

Document

DOI: 10.4230/LIPIcs.ECOOP.2021.11

Do Bugs Propagate? An Empirical Analysis of Temporal Correlations Among Software Bugs

Authors: Xiaodong Gu, Yo-Sub Han, Sunghun Kim, and Hongyu Zhang

Published in: LIPIcs, Volume 194, 35th European Conference on Object-Oriented Programming (ECOOP 2021)

Abstract

The 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.

Cite as

Xiaodong Gu, Yo-Sub Han, Sunghun Kim, and Hongyu Zhang. Do Bugs Propagate? An Empirical Analysis of Temporal Correlations Among Software Bugs. In 35th European Conference on Object-Oriented Programming (ECOOP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 194, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gu_et_al:LIPIcs.ECOOP.2021.11,
  author =	{Gu, Xiaodong and Han, Yo-Sub and Kim, Sunghun and Zhang, Hongyu},
  title =	{{Do Bugs Propagate? An Empirical Analysis of Temporal Correlations Among Software Bugs}},
  booktitle =	{35th European Conference on Object-Oriented Programming (ECOOP 2021)},
  pages =	{11:1--11:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-190-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{194},
  editor =	{M{\o}ller, Anders and Sridharan, Manu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2021.11},
  URN =		{urn:nbn:de:0030-drops-140540},
  doi =		{10.4230/LIPIcs.ECOOP.2021.11},
  annote =	{Keywords: empirical software engineering, bug propagation, software graph, bug correlation}
}

Search Results

Documents authored by Han, Yo-Sub

Simon’s Congruence Pattern Matching

Abstract

Cite as

Do Bugs Propagate? An Empirical Analysis of Temporal Correlations Among Software Bugs

Abstract

Cite as

Thanks for your feedback!

Could not send message