🇬🇧

The Degree of Word-Expansion of Lexicalized RRWW-Automata

Mráz, František
Plátek, Martin
Otto, Friedrich

Restarting automata can be seen as analytical variants of classical automata as well as of regulated rewriting systems. We study a measure for the degree of nondeterminism of (context-free) languages in terms of deterministic restarting automata that are (strongly) lexicalized. This measure is based on the number of auxiliary symbols (categories) used for recognizing a language as the projection of its characteristic language onto its input alphabet. This type of recognition is typical for analysis by reduction, a method used in linguistics for the creation and verification of formal descriptions of natural languages. Our main results establish a hierarchy of classes of context-free languages and two hierarchies of classes of non-context-free languages that are based on the expansion factor of a language.

Sponsor
F. Mráz and M.Plátek were supported by the program 'Information Society' under project 1ET100300517. F. Mráz was also supported by the Grant Agency of Charles University in Prague under Grant-No. 358/2006/A-INF/MFF. 
@techreport{urn:nbn:de:hebis:34-2007112619730,
  author    ={Mráz, František and Plátek, Martin and Otto, Friedrich},
  title    ={The Degree of Word-Expansion of Lexicalized RRWW-Automata},
  copyright  ={https://rightsstatements.org/page/InC/1.0/},
  language ={en},
  year   ={2007-11-26T12:52:38Z}
}