(Sub)regular robotic languages

摘要

This paper brings together concepts from linguistics and formal language theory and applies them to model robot behavior. This is done by defining a class of formal languages that capture the abstract behavior of robots which can be described as hybrid systems with stable continuous dynamics. It is shown that this class of languages falls within the Subregular hierarchy, thereby enabling computationally efficient operations between elements of the class. Specifically, we show that the languages in question are Star-free, but do not belong into two well known subclasses, members of which have been used in linguistics to construct models of natural language sound pattern acquisition.