generated from eliahuhorwitz/Academic-project-page-template
-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
225 lines (215 loc) · 10.8 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="description" content="Grammar Filtering For Syntax-Guided Synthesis">
<meta property="og:title" content="Grammar Filtering For Syntax-Guided Synthesis" />
<meta property="og:description"
content="Hybrid system using machine learning to preprocess Syntax Guided Synthesis (SyGuS) problems, reducing search space and enabling faster solutions." />
<meta property="og:url" content="URL OF THE WEBSITE" />
<meta property="og:image" content="static/images/your_banner_image.png" />
<meta property="og:image:width" content="1200" />
<meta property="og:image:height" content="630" />
<meta name="twitter:title" content="Grammar Filtering For Syntax-Guided Synthesis">
<meta name="twitter:description"
content="Hybrid system using machine learning to preprocess Syntax Guided Synthesis (SyGuS) problems, reducing search space and enabling faster solutions.">
<meta name="twitter:image" content="static/images/your_twitter_banner_image.png">
<meta name="twitter:card" content="summary_large_image">
<meta name="keywords" content="Program Synthesis, Syntax Guided Synthesis, Machine Learning, Programming-by-example">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Grammar Filtering For Syntax-Guided Synthesis</title>
<link rel="icon" type="image/x-icon" href="static/images/favicon.ico">
<link href="https://fonts.googleapis.com/css?family=Google+Sans|Noto+Sans|Castoro" rel="stylesheet">
<link rel="stylesheet" href="static/css/bulma.min.css">
<link rel="stylesheet" href="static/css/bulma-carousel.min.css">
<link rel="stylesheet" href="static/css/bulma-slider.min.css">
<link rel="stylesheet" href="static/css/fontawesome.all.min.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/jpswalsh/academicons@1/css/academicons.min.css">
<link rel="stylesheet" href="static/css/index.css">
<script src="https://ajax.googleapis.com/ajax/libs/jquery/3.5.1/jquery.min.js"></script>
<script src="https://documentcloud.adobe.com/view-sdk/main.js"></script>
<script defer src="static/js/fontawesome.all.min.js"></script>
<script src="static/js/bulma-carousel.min.js"></script>
<script src="static/js/bulma-slider.min.js"></script>
<script src="static/js/index.js"></script>
</head>
<body>
<section class="hero">
<div class="hero-body">
<div class="container is-max-desktop">
<div class="columns is-centered">
<div class="column has-text-centered">
<h1 class="title is-1 publication-title">Grammar Filtering For Syntax-Guided Synthesis</h1>
<div class="is-size-5 publication-authors">
<span class="author-block">
<a href="FIRST AUTHOR PERSONAL LINK" target="_blank">First Author</a><sup>*</sup>,</span>
<span class="author-block">
<a href="SECOND AUTHOR PERSONAL LINK" target="_blank">Second Author</a><sup>*</sup>,</span>
<span class="author-block">
<a href="THIRD AUTHOR PERSONAL LINK" target="_blank">Third Author</a>
</span>
</div>
<div class="is-size-5 publication-authors">
<span class="author-block">Institution Name<br>Conference name and year</span>
<span class="eql-cntrb"><small><br><sup>*</sup>Indicates Equal Contribution</small></span>
</div>
<div class="column has-text-centered">
<div class="publication-links">
<span class="link-block">
<a href="https://arxiv.org/pdf/<ARXIV PAPER ID>.pdf" target="_blank"
class="external-link button is-normal is-rounded is-dark">
<span class="icon">
<i class="fas fa-file-pdf"></i>
</span>
<span>Paper</span>
</a>
</span>
<span class="link-block">
<a href="static/pdfs/supplementary_material.pdf" target="_blank"
class="external-link button is-normal is-rounded is-dark">
<span class="icon">
<i class="fas fa-file-pdf"></i>
</span>
<span>Supplementary</span>
</a>
</span>
<span class="link-block">
<a href="https://github.com/YOUR REPO HERE" target="_blank"
class="external-link button is-normal is-rounded is-dark">
<span class="icon">
<i class="fab fa-github"></i>
</span>
<span>Code</span>
</a>
</span>
<span class="link-block">
<a href="https://arxiv.org/abs/<ARXIV PAPER ID>" target="_blank"
class="external-link button is-normal is-rounded is-dark">
<span class="icon">
<i class="ai ai-arxiv"></i>
</span>
<span>arXiv</span>
</a>
</span>
</div>
</div>
</div>
</div>
</div>
</div>
</section>
<!-- Paper abstract -->
<section class="section hero is-light">
<div class="container is-max-desktop">
<div class="columns is-centered has-text-centered">
<div class="column is-four-fifths">
<h2 class="title is-3">Abstract</h2>
<div class="content has-text-justified">
<p>
Programming-by-example (PBE) generates functions from input-output examples but is often too slow for
real-time use. Traditional approaches use automated reasoning tools or machine learning techniques. This
paper proposes a hybrid system using machine learning to preprocess Syntax Guided Synthesis (SyGuS)
problems, reducing search space and enabling faster solutions. The system reduces the runtime of the 2019
SyGuS Competition PBE Strings track winner by 47.65%, outperforming all competing tools.
</p>
</div>
</div>
</div>
</div>
</section>
<!-- End paper abstract -->
<!-- Paper introduction -->
<section class="section hero is-light">
<div class="container is-max-desktop">
<div class="columns is-centered has-text-centered">
<div class="column is-four-fifths">
<h2 class="title is-3">Introduction</h2>
<div class="content has-text-justified">
<p>
Program synthesis automatically generates code to meet specifications, focusing on what the code should
achieve rather than how it's implemented. Where the specifications can be given as a set of constraints,
inferred from program environments, or derived from large data sets. PBE exemplifies this approach, where
users provide input-output examples to generate code that generalizes beyond the given examples.
</p>
<p>
The Syntax Guided Synthesis (SyGuS) format standardizes synthesis problems, defining constraints and
grammars to construct programs. However, the real-world applications often require larger grammars,
impacting synthesis efficiency. Hence, as per experimentation it is found out that by manually removing
some parts of the grammar, the synthesis times can be improved.
</p>
</div>
</div>
</div>
</div>
</section>
<!-- End paper introduction -->
<!-- Paper background -->
<section class="section hero is-light">
<div class="container is-max-desktop">
<div class="columns is-centered has-text-centered">
<div class="column is-four-fifths">
<h2 class="title is-3">Background</h2>
<div class="content has-text-justified">
<p>
A SyGuS synthesis problem consists of a tuple (C, G) where C represents constraints, restricted to pairs
(i, o) of input-output examples within the domain of Programming by Example (PBE).
G is a context-free grammar from which terminal symbols (e.g., +, -, str.length) construct programs.
Notation π(G) denotes the set of terminal symbols in G.
</p>
<p>
SyGuS aims to find a program P ∈ G satisfying all constraints C. If found within time t, we write (G, C)→t
P; otherwise, (G, C)≠t P, with a typical timeout of 3600 seconds.
</p>
<p>
Gcrit, containing critical terminals for a solution, is also derived from G. The goal in this paper is to
identify a grammar G*, a reduced grammar where π(Gcrit) ⊆ π(G*) ⊆ π(G). This will minimize the search
space.
</p>
<figure>
<img src="static/images/image1.png" alt="Representation of how predicted grammar is generated">
<figcaption>Representation of how predicted grammar is generated</figcaption>
</figure>
</div>
</div>
</div>
</div>
</section>
<!-- End paper background -->
<!-- Paper conclusions -->
<section class="section hero is-light">
<div class="container is-max-desktop">
<div class="columns is-centered has-text-centered">
<div class="column is-four-fifths">
<h2 class="title is-3">Conclusions</h2>
<div class="content has-text-justified">
<p>
The approach this paper uses with GRT demonstrates substantial performance gains over existing SyGuS
solvers by leveraging neural network predictions to prune grammar terminals and improve synthesis
efficiency.
</p>
<p>
By encoding semantic approximations into the neural network trained on interpreter output data, the search
space is reduced without introducing new timeouts.
</p>
<p>
However, this paper can be improved, as currently it's predictions of time savings by removing terminals
relies on average expected values, which could benefit from more sophisticated neural network strategies
tailored to SyGuS problem constraints.
</p>
<figure>
<img src="static/images/visual.png"
alt="Image showing visual representation of finding a reduced grammar">
<figcaption>Image showing visual representation of finding a reduced grammar</figcaption>
</figure>
<figure>
<img src="static/images/image3.png" alt="Representation of 2 different types of solutions">
<figcaption>Representation of 2 different types of solutions</figcaption>
</figure>
</div>
</div>
</div>
</div>
</section>
<!-- End paper conclusions -->
</body>
</html>