We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Rational Index of Languages Defined by Grammars with Bounded Dimension of Parse Trees.
- Authors
Shemetova, Ekaterina; Okhotin, Alexander; Grigorev, Semyon
- Abstract
The rational index ρ L of a language L is an integer function, where ρ L (n) is the maximum length of the shortest string in L ∩ R , over all regular languages R recognized by n-state nondeterministic finite automata (NFA). This paper investigates the rational index of languages defined by grammars with bounded parse tree dimension: this is a numerical measure of the amount of branching in a tree (with trees in a linear grammar having dimension 1). For context-free grammars, a grammar with tree dimension bounded by d has rational index at most O (n 2 d) , and it is known from the literature that there exists a grammar with rational index Θ (n 2 d) . In this paper, it is shown that for multi-component grammars with at most k components (k-MCFG) and with a tree dimension bounded by d, the rational index is at most O (n 2 k d) , where the constant depends on the grammar, and there exists such a grammar with rational index k 2 k d 2 - k d - 2 k - 1 · (8 k + 1) 2 k d n 2 k d . Also, for the case of ordinary context-free grammars, a more precise lower bound 1 2 d 2 + d - 3 3 2 d n 2 d is established.
- Subjects
GRAMMAR; FINITE state machines; PARSING (Grammar); TREES; TREE branches
- Publication
Theory of Computing Systems, 2024, Vol 68, Issue 3, p487
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s00224-023-10159-3