检索结果-内蒙古大学图书馆

Repairing Regular Expressions for Extraction

PROCEEDINGS OF THE ACM ON programming LANGUAGES-PACMPL 2023年第PLDI期7卷 1633-1656页

作者： Chida, Nariyoshi Terauchi, Tachio Waseda Univ NTT Social Informat Labs Tokyo Japan Waseda Univ Tokyo Japan

While synthesizing and repairing regular expressions (regexes) based on programming-by-examples (PBE) methods have seen rapid progress in recent years, all existing works only support synthesizing or repairing regexes for membership testing, and the support for extraction is still an open problem. This paper fills the void by proposing the first PBE-based method for synthesizing and repairing regexes for extraction. Our work supports regexes that have real-world extensions such as backreferences and lookarounds. The extensions significantly affect the PBE-based synthesis and repair problem. In fact, we show that there are unsolvable instances of the problem if the synthesized regexes are not allowed to use the extensions, i.e., there is no regex without the extensions that correctly classify the given set of examples, whereas every problem instance is solvable if the extensions are allowed. This is in stark contrast to the case for the membership where every instance is guaranteed to have a solution expressible by a pure regex without the extensions. The main contribution of the paper is an algorithm to solve the PBE-based synthesis and repair problem for extraction. Our algorithm builds on existing methods for synthesizing and repairing regexes for membership testing, i.e., the enumerative search algorithms with SMT constraint solving. However, significant extensions are needed because the SMT constraints in the previous works are based on a non-deterministic semantics of regexes. Non-deterministic semantics is sound for membership but not for extraction, because which substrings are extracted depends on the deterministic behavior of actual regex engines. To address the issue, we propose a new SMT constraint generation method that respects the deterministic behavior of regex engines. For this, we first define a novel formal semantics of an actual regex engine as a deterministic big-step operational semantics, and use it as a basis to design the new SMT constraint g

关键词： Regular Expression programming by example Program Repair

来源：评论

学校读者我要写书评

暂无评论

Training agents to recognize text by example

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2001年第1-2期4卷 79-92页

作者： Lieberman, H Nardi, BA Wright, DJ MIT Media Lab Cambridge MA 02139 USA AT&T Labs W Menlo Park CA USA Apple Comp Inc Cupertino CA 95014 USA

An important function of an agent is to be "on the lookout" for bits of information that are interesting to its user, even if these items appear in the midst of a larger body of unstructured information. But how to tell these agents which patterns are meaningful and what to do with the result? Especially when agents are used to recognize text, they are usually driven by parsers which require input in the form of textual grammar rules. Editing grammars is difficult and error-prone for end users. Grammar ["Grammars by example"] is the first direct manipulation interface designed to allow nonexpert users to define grammars interactively. The user presents concrete examples of text that he or she would like the agent to recognize. Rules are constructed by an iterative process, where Grammex heuristically parses the example, displays a set of hypotheses, and the user critiques the system's suggestions. Actions to take upon recognition are also demonstrated by example.

关键词： agents parsers grammars programming by example programming by demonstration

来源：评论

学校读者我要写书评

暂无评论

Combining the Top-Down Propagation and Bottom-Up Enumeration for Inductive Program Synthesis

引用

PROCEEDINGS OF THE ACM ON programming LANGUAGES-PACMPL 2021年第POPL期5卷 1–28页

作者： Lee, Woosuk Hanyang Univ Coll Comp Seoul South Korea

We present an effective method for scalable and general-purpose inductive program synthesis. There have been two main approaches for inductive synthesis: enumerative search, which repeatedly enumerates possible candidate programs, and the top-down propagation (TDP), which recursively decomposes a given large synthesis problem into smaller subproblems. Enumerative search is generally applicable but limited in scalability, and the TDP is efficient but only works for special grammars or applications. In this paper, we synergistically combine the two approaches. We generate small program subexpressions via enumerative search and put them together into the desired program by using the TDP. Enumerative search enables to bring the power of TDP into arbitrary grammars, and the TDP helps to overcome the limited scalability of enumerative search. We apply our approach to a standard formulation, syntax-guided synthesis (SyGuS), thereby supporting a broad class of inductive synthesis problems. We have implemented our approach in a tool called Duet and evaluate it on SyGuS benchmark problems from various domains. We show that Duet achieves significant performance gains over existing general-purpose as well as domain-specific synthesizers.

关键词： programming by example Syntax-guided Synthesis

来源：评论

学校读者我要写书评

暂无评论

Feedback-Driven Semi-supervised Synthesis of Program Transformations

引用

PROCEEDINGS OF THE ACM ON programming LANGUAGES-PACMPL 2020年第OOPSLA期4卷 1–30页

作者： Gao, Xiang Barke, Shraddha Radhakrishna, Arjun Soares, Gustavo Gulwani, Sumit Leung, Alan Nagappan, Nachiappan Tiwari, Ashish Natl Univ Singapore Singapore Singapore Univ Calif San Diego San Diego CA 92103 USA Microsoft Redmond WA USA

While editing code, it is common for developers to make multiple related repeated edits that are all instances of a more general program transformation. Since this process can be tedious and error-prone, we study the problem of automatically learning program transformations from past edits, which can then be used to predict future edits. We take a novel view of the problem as a semi-supervised learning problem: apart from the concrete edits that are instances of the general transformation, the learning procedure also exploits access to additional inputs (program subtrees) that are marked as positive or negative depending on whether the transformation applies on those inputs. We present a procedure to solve the semi-supervised transformation learning problem using anti-unification and programming-by-example synthesis technology. To eliminate reliance on access to marked additional inputs, we generalize the semi-supervised learning procedure to a feedback-driven procedure that also generates the marked additional inputs in an iterative loop. We apply these ideas to build and evaluate three applications that use different mechanisms for generating feedback. Compared to existing tools that learn program transformations from edits, our feedback-driven semi-supervised approach is vastly more effective in successfully predicting edits with significantly lesser amounts of past edit data.

关键词： Program transformation Refactoring Program synthesis programming by example

来源：评论

学校读者我要写书评

暂无评论

Mobius: Synthesizing Relational Queries with Recursive and Invented Predicates

引用

PROCEEDINGS OF THE ACM ON programming LANGUAGES-PACMPL 2023年第OOPSLA期7卷 1394–1417页

作者： Thakkar, Aalok Sands, Nathaniel Petrou, George Alur, Rajeev Naik, Mayur Raghothaman, Mukund Univ Penn Philadelphia PA 19104 USA Univ Southern Calif Los Angeles CA USA

Synthesizing relational queries from data is challenging in the presence of recursion and invented predicates. We propose a fully automated approach to synthesize such queries. Our approach comprises of two steps: it first synthesizes a non-recursive query consistent with the given data, and then identifies recursion schemes in it and thereby generalizes to arbitrary data. This generalization is achieved by an iterative predicate unification procedure which exploits the notion of data provenance to accelerate convergence. In each iteration of the procedure, a constraint solver proposes a candidate query, and a query evaluator checks if the proposed program is consistent with the given data. The data provenance for a failed query allows us to construct additional constraints for the constraint solver and refine the search. We have implemented our approach in a tool named MOBIUS. On a suite of 21 challenging recursive query synthesis tasks, MOBIUS outperforms three state-of-the-art baselines GENSYNTH, ILASP, and POPPER, both in terms of runtime and accuracy. We also demonstrate that the synthesized queries generalize well to unseen data.

关键词： programming by example example-guided synthesis recursive program synthesis

来源：评论

学校读者我要写书评

暂无评论

Data Quality Challenge: Toward a Tool for String Processing by examples

引用

ACM JOURNAL OF DATA AND INFORMATION QUALITY 2015年第4期6卷 1–4页

作者： Bartoli, Alberto De Lorenzo, Andrea Medvet, Eric Tarlao, Fabiano Univ Trieste DIA Trieste Italy Univ Trieste Dip Ingn Architettura Via Valerio 10 I-34125 Trieste Italy

来源：评论

学校读者我要写书评

暂无评论

Empowering Children To Rapidly Author Games and Animations Without Writing Code 16

Empowering Children To Rapidly Author Games and Animations W...

引用

15th International ACM Conference on Interaction Design and Children (IDC)

作者： Banerjee, Rahul Yip, Jason Lee, Kung Jin Popovic, Zoran Univ Washington Ctr Game Sci Comp Sci & Engn Seattle WA 98195 USA Univ Washington Informat Sch Seattle WA 98195 USA

ISBN: (纸本)9781450343138

Prior research has established that long-term interests in programming are often shaped by formative computing experiences, especially those involving programming and graphics. Existing authoring environments for children (ages 9-14) to make 2D games and animations require them to: (a) create programs, (b) customize templates, or (c) combine rewrite rules with programs. One way to support early experiences in computing for a more diverse set of learners is to simplify such authoring systems, by removing text heavy code and minimizing cognitive load, which can allow separation of coding concepts from writing code. In this paper, we describe an exploratory system we are designing to test this idea, called BlockStudio. Using a programming by example paradigm, children manipulate colored blocks on the screen to specify desired behavior via concrete changes. Based on these inputs, our system synthesizes generalized rules based on color. We give a brief overview of our current prototype, then share insights gleaned from two intergenerational co-design sessions with children and discuss implications for designers of similar systems.

关键词： Authoring games interactive content programming by example rule-based system user interface

来源：评论

学校读者我要写书评

暂无评论

Synthesizing Regular Expressions from examples for Introductory Automata Assignments 2016

Synthesizing Regular Expressions from Examples for Introduct...

引用

15th ACM International Conference on Generative programming - Concepts and Experiences (GPCE)

作者： Lee, Mina So, Sunbeom Oh, Hakjoo Korea Univ Seoul South Korea

ISBN: (纸本)9781450344463

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.

关键词： Regular expression program synthesis programming by example

来源：评论

学校读者我要写书评

暂无评论

Component-Based Synthesis of Table Consolidation and Transformation Tasks from examples 2017

Component-Based Synthesis of Table Consolidation and Transfo...

引用

38th ACM SIGPLAN Conference on programming Language Design and Implementation (PLDI)

作者： Feng, Yu Martins, Ruben Van Geffen, Jacob Dillig, Isil Chaudhuri, Swarat Univ Texas Austin Austin TX 78712 USA Rice Univ Houston TX 77251 USA

ISBN: (纸本)9781450349888

This paper presents a novel component-based synthesis algorithm that marries the power of type-directed search with lightweight SMT-based deduction and partial evaluation. Given a set of components together with their over-approximate first-order specifications, our method first generates a program sketch over a subset of the components and checks its feasibility using an SMT solver. Since a program sketch typically represents many concrete programs, the use of SMT-based deduction greatly increases the scalability of the algorithm. Once a feasible program sketch is found, our algorithm completes the sketch in a bottom-up fashion, using partial evaluation to further increase the power of deduction for rejecting partially-filled program sketches. We apply the proposed synthesis methodology for automating a large class of data preparation tasks that commonly arise in data science. We have evaluated our synthesis algorithm on dozens of data wrangling and consolidation tasks obtained from on-line forums, and we show that our approach can automatically solve a large class of problems encountered by R users.

关键词： Program synthesis programming by example data preparation Component-based synthesis SMT-based deduction

来源：评论

学校读者我要写书评

暂无评论

End-User programming Architecture for Physical Movement Assessment: An Interactive Machine Learning Approach 11th

End-User Programming Architecture for Physical Movement Asse...

引用

11th International Conference on Digital Human Modeling and Applications in Health, Safety, Ergonomics and Risk Management (DHM) Held as Part of the 22nd International Conference on Human-Computer Interaction (HCII)

作者： Palomares-Pecho, Jessica M. Silva-Calpa, Greis Francy M. Sierra-Franco, Cesar A. Raposo, Alberto Barbosa Pontifical Catholic Univ Rio de Janeiro PUC Rio Dept Informat BR-22451900 Gavea RJ Brazil Pontifical Catholic Univ Rio de Janeiro PUC Rio Tecgraf Inst BR-22451900 Gavea RJ Brazil

ISBN: (纸本)9783030499037;9783030499044

In this article, we propose an end-user adaptive architecture for movement assessment from RGB videos. Our method allows physiotherapists to add customized exercises for patients from only a few video training examples. The main idea is to take leverage of Deep learning-based pose estimation frameworks to track in real-time the key-body joints from the image data. Our system mimics the traditional physical rehabilitation process, where the therapist guides patients through demonstrative examples, and the patients repeat these examples while the physiotherapist monitors their movements. We evaluate our proposed method on four physiotherapeutic exercises for shoulder strengthening. Results indicate that our approach contributes both to reduce physiotherapist time needed to train the system, and to automatically assess the patients' movements without direct monitoring from the physiotherapist.

关键词： Interactive Machine learning OpenPose programming by example Rehabilitation Human activity recognition

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：