A Tree Sampler for Bounded Context-Free Languages
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911984422748160 |
|---|---|
| author | Considine, Breandan |
| author_facet | Considine, Breandan |
| contents | In the following paper, we present a simple method for sampling trees with or without replacement from BCFLs. A BCFL is a context-free language (CFL) corresponding to an incomplete string with holes, which can be completed by valid terminals. To solve this problem, we introduce an algebraic datatype that compactly represents candidate parse forests for porous strings. Once constructed, sampling trees is a straightforward matter of sampling integers uniformly without replacement, then lazily decoding them into trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_01849 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Tree Sampler for Bounded Context-Free Languages Considine, Breandan Formal Languages and Automata Theory In the following paper, we present a simple method for sampling trees with or without replacement from BCFLs. A BCFL is a context-free language (CFL) corresponding to an incomplete string with holes, which can be completed by valid terminals. To solve this problem, we introduce an algebraic datatype that compactly represents candidate parse forests for porous strings. Once constructed, sampling trees is a straightforward matter of sampling integers uniformly without replacement, then lazily decoding them into trees. |
| title | A Tree Sampler for Bounded Context-Free Languages |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2408.01849 |