2023/10/19 by Xiang Li, Li, Xiang, Xiangyu Zhou +7 · 1 citation
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Logic, programming, and type systems #Programming Languages (cs.PL) #Software Engineering (cs.SE) #Software Engineering Research #Software Testing and Debugging Techniques
paper · pdf · doi:10.48550/arxiv.2311.03705
openalex publication_date 2023/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose a novel synthesis algorithm that can efficiently search programs with context-dependent semantics (i.e., open programs with free variables that require a binding context to be evaluated), in the context of web automation. Notably, our algorithm can search programs using non-input variables (which are local variables introduced by the program) more efficiently than prior work. Our contributions are twofold. First, we generalize the standard (context-unaware) observational equivalence (OE) from the program synthesis literature to context-aware OE, by taking into account non-input variables. Second (and more importantly), we describe an algorithm that can use context-aware OE to reduce a significantly broader class of programs. These ideas are instantiated in the domain of web automation. The resulting tool, Arborist, can automate a broader range of challenging tasks more efficiently than the state-of-the-art.