Non-Self-Embedding Grammars and Descriptional Complexity
| العنوان: | Non-Self-Embedding Grammars and Descriptional Complexity |
|---|---|
| المؤلفون: | Giovanni Pighizzini, Luca Prigioniero |
| المصدر: | Fundamenta Informaticae. 180:103-122 |
| بيانات النشر: | IOS Press, 2021. |
| سنة النشر: | 2021 |
| مصطلحات موضوعية: | TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Algebra and Number Theory, Self-embedding, Theoretical computer science, Computational Theory and Mathematics, Rule-based machine translation, Computer science, Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), Computer Science::Formal Languages and Automata Theory, Information Systems, Theoretical Computer Science |
| الوصف: | Non-self-embedding grammars are a subclass of context-free grammars which only generate regular languages. The size costs of the conversion of non-self-embedding grammars into equivalent finite automata are studied, by proving optimal bounds for the number of states of nondeterministic and deterministic automata equivalent to given non-self-embedding grammars. In particular, each non-self-embedding grammar of size s can be converted into an equivalent nondeterministic automaton which has an exponential size in s and into an equivalent deterministic automaton which has a double exponential size in s. These costs are shown to be optimal. Moreover, they do not change if the larger class of quasi-non-self-embedding grammars, which still generate only regular languages, is considered. In the case of letter bounded languages, the cost of the conversion of non-self-embedding grammars and quasi-non-self-embedding grammars into deterministic automata reduces to an exponential of a polynomial in s. |
| تدمد: | 1875-8681 0169-2968 |
| DOI: | 10.3233/fi-2021-2036 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::947f1d596fc3185a95639370a7ee56ca https://doi.org/10.3233/fi-2021-2036 |
| رقم الانضمام: | edsair.doi...........947f1d596fc3185a95639370a7ee56ca |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 18758681 01692968 |
|---|---|
| DOI: | 10.3233/fi-2021-2036 |