DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2022.50

A Robust Class of Languages of 2-Nested Words

Authors: Séverine Fratani, Guillaume Maurras, and Pierre-Alain Reynier

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

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.

Cite as

Séverine Fratani, Guillaume Maurras, and Pierre-Alain Reynier. A Robust Class of Languages of 2-Nested Words. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.MFCS.2022.50},
  URN =		{urn:nbn:de:0030-drops-168485},
  doi =		{10.4230/LIPIcs.MFCS.2022.50},
  annote =	{Keywords: Nested word, Determinization, Indexed languages}
}

Search Results

Documents authored by Fratani, Séverine

A Robust Class of Languages of 2-Nested Words

Abstract

Cite as

Thanks for your feedback!

Could not send message