Streamability of nested word transductions by Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, Frédéric Servais

“…We consider the problem of evaluating in streaming (i.e., in a single left-to-right pass) a nested word transduction with a limited amount of memory. …”
Get full text

First-Order and Temporal Logics for Nested Words by Rajeev Alur, Marcelo Arenas, Pablo Barcelo, Kousha Etessami, Neil Immerman, Leonid Libkin

“…Nested words are a structured model of execution paths in procedural programs, reflecting their call and return nesting structure. …”
Get full text

Determinization and Minimization of Automata for Nested Words Revisited by Joachim Niehren, Momar Sakho

Subjects: Get full text

Weighted Logics for Nested Words and Algebraic Formal Power Series by Christian Mathissen

“…In this paper we introduce quantitative extensions and study nested word series which assign to nested words elements of a semiring. …”
Get full text

Expressiveness of Visibly Pushdown Transducers by Mathieu Caralp, Emmanuel Filiot, Pierre-Alain Reynier, Frédéric Servais, Jean-Marc Talbot

“…They have been introduced to model transformations of nested words, i.e. words with a call/return structure. …”
Get full text

A First-Order Complete Temporal Logic for Structured Context-Free Languages by Michele Chiari, Dino Mandrioli, Matteo Pradella

“…The most notable of such results are temporal logics on Nested Words, such as CaRet and NWTL. Recently, the logic OPTL was introduced, based on the class of Operator Precedence Languages (OPLs), more powerful than Nested Words. …”
Get full text

DIctionnaire Synchronique des FAmilles dérivationnelles de mots français (DISFA) jako faza ewolucji słowotwórstwa gniazdowego by Wanda Fijałkowska

“…DI ctionnaire Synchronique des FAmilles derivationnelles de mots français (DISFA) as a phase in the evolution of nest word formation The lexicography of the Slavonic nations, especially the branch of nest lexicography, has seen an impetuous development since the sixties, producing at least fifty publications, but it remains effectively unknown to French lexicography. …”
Get full text

The μ-Calculus Alternation Hierarchy Collapses over Structures with Restricted Connectivity by Julian Gutierrez, Felix Klaedtke, Martin Lange

“…This paper makes progress in answering these questions by showing that the alternation hierarchy of the mu-calculus collapses to the alternation-free fragment over some classes of structures, including infinite nested words and finite graphs with feedback vertex sets of a bounded size. …”
Get full text

Synthesis from Recursive-Components Libraries by Yoad Lustig, Moshe Vardi

“…We define the problem of Nested-Words Temporal Logic (NWTL) synthesis from recursive component libraries, where NWTL is a specification formalism, richer than LTL, that is suitable for ``call and return'' computations. …”
Get full text

The μ-calculus alternation hierarchy collapses over structures with restricted connectivity by Gutierrez, J, Klaedtke, F, Lange, M

“…This article makes progress in answering these questions by showing that the alternation hierarchy of the μ-calculus collapses to the alternation-free fragment over some classes of structures, including infinite nested words and finite graphs with feedback vertex sets of a bounded size. …”

On the Expressive Power of 2-Stack Visibly Pushdown Automata by Benedikt Bollig

“…Finally, we discuss the expressive power of B\"{u}chi 2-stack visibly pushdown automata running on infinite (nested) words. Extending the logic by an infinity quantifier, we can likewise establish equivalence to existential monadic second-order logic.…”
Get full text

On collapsible pushdown automata, their graphs and the power of links by Broadbent, C, Christopher Broadbent

“…We introduce prefix-rewrite systems for nested-words that characterise the configuration graphs of both 2-CPDA and 2-HOPDA, capturing the power of collapse precisely in terms outside of the language of CPDA. …”