Projects per year
Abstract
Nested words provide a natural model of runs of programs with recursive procedure calls. The usual connection between monadic secondorder logic (MSO) and automata extends from words to nested words and gives us a natural notion of regular languages of nested words.
In this paper we look at some wellknown 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 mucalculus is as expressive as MSO over finite and infinite nested words, and the equivalence holds, more generally, for mucalculus 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 lettertoletter 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.
In this paper we look at some wellknown 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 mucalculus is as expressive as MSO over finite and infinite nested words, and the equivalence holds, more generally, for mucalculus 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 lettertoletter 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.
Original language  English 

Pages (fromto)  639670 
Number of pages  32 
Journal  Theory of Computing Systems 
Volume  49 
Issue number  3 
DOIs  
Publication status  Published  Oct 2011 
Fingerprint
Dive into the research topics of 'Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization'. Together they form a unique fingerprint.Projects
 1 Finished

XML with Incomplete Information: Representation, Querying and Applications
1/09/09 → 30/11/13
Project: Research