Weighted automata and logics for infinite nested words

DOI10.1007/978-3-319-04921-2_26zbMATH Open1364.68249arXiv1506.07031OpenAlexW2419671704MaRDI QIDQ515684FDOQ515684

Authors: Manfred Droste, Stefan Dück 

Publication date: 16 March 2017

Published in: Information and Computation, Language and Automata Theory and Applications (Search for Journal in Brave)

Abstract: Nested words introduced by Alur and Madhusudan are used to capture structures with both linear and hierarchical order, e.g. XML documents, without losing valuable closure properties. Furthermore, Alur and Madhusudan introduced automata and equivalent logics for both finite and infinite nested words, thus extending B"uchi's theorem to nested words. Recently, average and discounted computations of weights in quantitative systems found much interest. Here, we will introduce and investigate weighted automata models and weighted MSO logics for infinite nested words. As weight structures we consider valuation monoids which incorporate average and discounted computations of weights as well as the classical semirings. We show that under suitable assumptions, two resp. three fragments of our weighted logics can be transformed into each other. Moreover, we show that the logic fragments have the same expressive power as weighted nested word automata.

Full work available at URL: https://arxiv.org/abs/1506.07031

Recommendations

• Weighted automata and weighted logics on infinite words
• Weighted Automata and Weighted Logics on Infinite Words
• Weighted automata and logics on infinite graphs
• Weighted nested word automata and logics over strong bimonoids
• Weighted nested word automata and logics over strong bimonoids
• Weighted automata and weighted logics
• Automata, Languages and Programming
• Weighted automata and weighted logics
• Automata and Logics for Words and Trees over an Infinite Alphabet

zbMATH Keywords

weighted automatanested wordsweighted logicsquantitative automatavaluation monoids

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Cites Work

• Title not available (Why is that?)
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Handbook of weighted automata
• Adding nesting structure to words
• Title not available (Why is that?)
• On the definition of a family of automata
• Title not available (Why is that?)
• Weak Second‐Order Arithmetic and Finite Automata
• Title not available (Why is that?)
• Decision Problems of Finite Automata Design and Related Arithmetics
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Weighted versus Probabilistic Logics
• Quantitative Languages
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Tree acceptors and some of their applications
• First-Order and Temporal Logics for Nested Words
• Weighted automata and weighted MSO logics for average and long-time behaviors
• Weighted automata and weighted logics
• Weighted automata and multi-valued logics over arbitrary bounded lattices
• Weighted logics for unranked tree automata
• Weighted nested word automata and logics over strong bimonoids
• Weighted Tree Automata over Valuation Monoids and Their Characterization by Weighted Logics
• Weighted Logics for Nested Words and Algebraic Formal Power Series
• Weighted Automata and Weighted Logics on Infinite Words
• Title not available (Why is that?)
• Weighted tree automata and weighted logics

This page was built for publication: Weighted automata and logics for infinite nested words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q515684)