External contextual grammars with resources restricted and structure limited selection
Abstract
In this paper, we continue the research on the power of contextual grammars with selection languages from subfamilies of the family of regular languages. In the past, two independent hierarchies have been obtained for external and internal contextual grammars, one based on selection languages defined by structural properties (finite, monoidal, nilpotent, combinational, definite, ordered, non-counting, power-separating, suffix-closed, commutative, circular, or union-free languages), the other one based on selection languages defined by resources (number of non-terminal symbols, production rules, or states needed for generating or accepting them). In the present paper, we compare the language families of these hierarchies for external contextual grammars and merge the hierarchies.
Fields of Study & Subjects
semigroups and automata theory
Syntax
Semantics
Linguistic Variation
Algorithms and Data Compression
Publication details
- Journal / source
- Information and Computation
- Volume
- 310
- Pages
- 105439–105439
- Publication date
- 13 March 2026
- Language
- EN