External contextual grammars with resources restricted and structure limited selection

Read full text
Authors: Bianca Truthe
Cited by: 0
References: 7

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