论文标题
一类强大的2个词语语言
A robust class of languages of 2-nested words
论文作者
论文摘要
常规的嵌套单词语言（又名可见下降语言）严格扩展常规单词语言，同时保留其主要的闭合和可定性属性。先前的作品表明，考虑2个词语单词的语言，即具有两种匹配的单词（又称2个可见的下降语言），并不成功：在确定性下，自动机的相应模型并未关闭。在这项工作中，受索引语言的同态表示的启发，我们确定了一个2个nest词的子类，我们称之为2波单词。该类严格地扩展了嵌套单词的类，同时保留其主要属性。更准确地说，我们在确定相应的自动机模型的确定下证明了闭合，我们提供了公认的语言的逻辑表征，并证明相应的图具有有界的treewidth。结果，我们得出了重要的闭合和可决定性。最后，我们证明了我们定义的语言的单词投影属于线性索引语言的类别。
Regular nested word languages (a.k.a. visibly pushdown languages) strictly extend regular word languages, while preserving their main closure and decidability properties. Previous works have shown that considering languages of 2-nested words, i.e. words enriched with two matchings (a.k.a. 2-visibly pushdown languages), is not as successful: the corresponding model of automata is not closed under determinization. In this work, inspired by homomorphic representations of indexed languages, we identify a subclass of 2-nested words, which we call 2-wave words. This class strictly extends the class of nested words, while preserving its main properties. More precisely, we prove closure under determinization of the corresponding automaton model, we provide a logical characterization of the recognized languages, and show that the corresponding graphs have bounded treewidth. As a consequence, we derive important closure and decidability properties. Last, we show that the word projections of the languages we define belong to the class of linear indexed languages.
