Properties and Limits of Supercombinator Set Acquired from Context-free Grammar Samples
| Autor: | Ján Kollár, Michal Sicak |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Computer science
020207 software engineering Operator-precedence grammar 02 engineering and technology Mildly context-sensitive grammar formalism Context-free grammar Set (abstract data type) Grammar-based code Affix grammar Regular tree grammar 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Limit (mathematics) Algorithm |
| Zdroj: | FedCSIS |
| ISSN: | 2300-5963 |
| DOI: | 10.15439/2017f249 |
| Popis: | We present an improved version of algorithm that can transform any context-free grammar into a supercombinator form. Such a form is composed only of lambda calculus' supercombinators that are enriched by grammar operations. The main properties of this form are non-redundancy and scalability. We show the improvements that we've made to create smaller supercombinator set than in our previous algorithm's version. We present experiments performed on Context-free grammars obtained by transformation from Groningen meaning bank corpus. Experiments confirm that our form has a theoretical maximum limit of possible supercombinators. That limit is a mathematical sequence called Catalan number. We show that in some cases we are able to reach that limit if we use large enough input data source and we limit the size of supercombinator permitted into the final set. We also describe another benefit of our algorithm, which is the identification of most reoccurring structures in the input set. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|