License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.50
URN: urn:nbn:de:0030-drops-168485
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16848/
Go to the corresponding LIPIcs Volume Portal

Fratani, Séverine ; Maurras, Guillaume ; Reynier, Pierre-Alain

A Robust Class of Languages of 2-Nested Words

pdf-format:
LIPIcs-MFCS-2022-50.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{fratani_et_al:LIPIcs.MFCS.2022.50,
  author =	{Fratani, S\'{e}verine and Maurras, Guillaume and Reynier, Pierre-Alain},
  title =	{{A Robust Class of Languages of 2-Nested Words}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{50:1--50:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16848},
  URN =		{urn:nbn:de:0030-drops-168485},
  doi =		{10.4230/LIPIcs.MFCS.2022.50},
  annote =	{Keywords: Nested word, Determinization, Indexed languages}
}

Keywords: Nested word, Determinization, Indexed languages
Collection: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Issue Date: 2022
Date of publication: 22.08.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI