2026-07-23T22:06:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16848 2024-03-06T10:58:29Z ddc:004 open_access

A Robust Class of Languages of 2-Nested Words Fratani, Séverine Maurras, Guillaume Reynier, Pierre-Alain Nested word Determinization Indexed languages 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Séverine Fratani and Guillaume Maurras and Pierre-Alain Reynier 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.50 urn:nbn:de:0030-drops-168485 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.50 eng https://creativecommons.org/licenses/by/4.0/legalcode