Synthesizing regular expressions from examples for introductory automata assignments
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Lee, M. | - |
dc.contributor.author | So, S. | - |
dc.contributor.author | Oh, H. | - |
dc.date.accessioned | 2021-09-04T08:48:47Z | - |
dc.date.available | 2021-09-04T08:48:47Z | - |
dc.date.created | 2021-06-17 | - |
dc.date.issued | 2016 | - |
dc.identifier.issn | 1523-2867 | - |
dc.identifier.uri | https://scholar.korea.ac.kr/handle/2021.sw.korea/91367 | - |
dc.description.abstract | We present a method for synthesizing regular expressions for introductory automata assignments. Given a set of positive and negative examples, the method automatically synthesizes the simplest possible regular expression that accepts all the positive examples while rejecting all the negative examples. The key novelty is the search-based synthesis algorithm that leverages ideas from over- and under-approximations to effectively prune out a large search space. We have implemented our technique in a tool and evaluated it with non-trivial benchmark problems that students often struggle with. The results show that our system can synthesize desired regular expressions in 6.7 seconds on the average, so that it can be interactively used by students to enhance their understanding of regular expressions. © 2016 ACM. | - |
dc.language | English | - |
dc.language.iso | en | - |
dc.publisher | Association for Computing Machinery | - |
dc.subject | Approximation algorithms | - |
dc.subject | Automata theory | - |
dc.subject | Bench-mark problems | - |
dc.subject | Negative examples | - |
dc.subject | Positive examples | - |
dc.subject | Regular expressions | - |
dc.subject | Search spaces | - |
dc.subject | Search-based | - |
dc.subject | Synthesis algorithms | - |
dc.subject | Under-approximation | - |
dc.subject | Pattern matching | - |
dc.title | Synthesizing regular expressions from examples for introductory automata assignments | - |
dc.type | Article | - |
dc.contributor.affiliatedAuthor | Oh, H. | - |
dc.identifier.doi | 10.1145/2993236.2993244 | - |
dc.identifier.scopusid | 2-s2.0-85084175881 | - |
dc.identifier.bibliographicCitation | ACM SIGPLAN Notices, v.52, no.3, pp.70 - 80 | - |
dc.relation.isPartOf | ACM SIGPLAN Notices | - |
dc.citation.title | ACM SIGPLAN Notices | - |
dc.citation.volume | 52 | - |
dc.citation.number | 3 | - |
dc.citation.startPage | 70 | - |
dc.citation.endPage | 80 | - |
dc.type.rims | ART | - |
dc.type.docType | Article | - |
dc.description.journalClass | 1 | - |
dc.description.journalRegisteredClass | scopus | - |
dc.subject.keywordPlus | Approximation algorithms | - |
dc.subject.keywordPlus | Automata theory | - |
dc.subject.keywordPlus | Bench-mark problems | - |
dc.subject.keywordPlus | Negative examples | - |
dc.subject.keywordPlus | Positive examples | - |
dc.subject.keywordPlus | Regular expressions | - |
dc.subject.keywordPlus | Search spaces | - |
dc.subject.keywordPlus | Search-based | - |
dc.subject.keywordPlus | Synthesis algorithms | - |
dc.subject.keywordPlus | Under-approximation | - |
dc.subject.keywordPlus | Pattern matching | - |
dc.subject.keywordAuthor | program synthesis | - |
dc.subject.keywordAuthor | programming by example | - |
dc.subject.keywordAuthor | Regular expression | - |
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
(02841) 서울특별시 성북구 안암로 14502-3290-1114
COPYRIGHT © 2021 Korea University. All Rights Reserved.
Certain data included herein are derived from the © Web of Science of Clarivate Analytics. All rights reserved.
You may not copy or re-distribute this material in whole or in part without the prior written consent of Clarivate Analytics.