TY - JOUR

T1 - Rational Index of Languages Defined by Grammars with Bounded Dimension of Parse Trees

AU - Шеметова, Екатерина Николаевна

AU - Охотин, Александр Сергеевич

AU - Григорьев, Семен Вячеславович

PY - 2024/6/1

Y1 - 2024/6/1

N2 - 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(n2d) , and it is known from the literature that there exists a grammar with rational index Θ (n2d) . 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(n2kd) , where the constant depends on the grammar, and there exists such a grammar with rational index k2kd2-kd-2k-1·(8k+1)2kdn2kd . Also, for the case of ordinary context-free grammars, a more precise lower bound 12d2+d-332dn2d is established.

AB - 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(n2d) , and it is known from the literature that there exists a grammar with rational index Θ (n2d) . 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(n2kd) , where the constant depends on the grammar, and there exists such a grammar with rational index k2kd2-kd-2k-1·(8k+1)2kdn2kd . Also, for the case of ordinary context-free grammars, a more precise lower bound 12d2+d-332dn2d is established.

KW - Context-free grammars

KW - Dimension of a parse tree

KW - Multiple context-free grammars

KW - Quasi-rational languages

KW - Rational index

KW - Strahler number

KW - k-caterpillar trees

UR - https://www.mendeley.com/catalogue/a1169f90-befa-34b9-9727-a49d018725ba/

U2 - 10.1007/s00224-023-10159-3

DO - 10.1007/s00224-023-10159-3

M3 - Article

VL - 68

SP - 487

EP - 511

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 3

ER -