Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization

Simple item page
dc.contributor.authorArenas, Marcelo
dc.contributor.authorBarcelo, Pablo
dc.contributor.authorLibkin, Leonid
dc.date.accessioned2025-01-21T00:00:42Z
dc.date.available2025-01-21T00:00:42Z
dc.date.issued2011
dc.description.abstractNested words provide a natural model of runs of programs with recursive procedure calls. The usual connection between monadic second-order logic (MSO) and automata extends from words to nested words and gives us a natural notion of regular languages of nested words.
dc.description.abstractIn this paper we look at some well-known aspects of regular languages-their characterization via fixed points, deterministic and alternating automata for them, and synchronization for defining regular relations-and extend them to nested words. We show that mu-calculus is as expressive as MSO over finite and infinite nested words, and the equivalence holds, more generally, for mu-calculus with past modalities evaluated in arbitrary positions in a word, not only in the first position. We introduce the notion of alternating automata for nested words, show that they are as expressive as the usual automata, and also prove that Muller automata can be determinized (unlike in the case of visibly pushdown languages). Finally we look at synchronization over nested words. We show that the usual letter-to-letter synchronization is completely incompatible with nested words (in the sense that even the weakest form of it leads to an undecidable formalism) and present an alternative form of synchronization that gives us decidable notions of regular relations.
dc.fuente.origenWOS
dc.identifier.doi10.1007/s00224-010-9292-5
dc.identifier.eissn1433-0490
dc.identifier.issn1432-4350
dc.identifier.urihttps://doi.org/10.1007/s00224-010-9292-5
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/95353
dc.identifier.wosidWOS:000293247300007
dc.issue.numero3
dc.language.isoen
dc.pagina.final670
dc.pagina.inicio639
dc.revistaTheory of computing systems
dc.rightsacceso restringido
dc.subjectAutomata
dc.subjectNested words
dc.subjectMu-calculus
dc.subjectQuery languages
dc.subjectAutomatic structures
dc.titleRegular Languages of Nested Words: Fixed Points, Automata, and Synchronization
dc.typeartículo
dc.volumen49
sipa.indexWOS
sipa.trazabilidadWOS;2025-01-12
Files
Collections
Artículos de revistas