Weighted nested word automata and logics over strong bimonoids
type: Item
instance of: scholarly article
zbMATH Open document ID: 1310.68129
DOI: 10.1142/S0129054114500269
author: Bundit Pibaljommee
author: Manfred Droste
published in: International Journal of Foundations of Computer Science
publication date: 2014-11-14T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 68Q70
zbMATH DE Number: 6369423
zbMATH Keywords: weighted automata
zbMATH Keywords: nested words
zbMATH Keywords: nested automata
zbMATH Keywords: bimonoids
zbMATH Keywords: weighted logics
zbMATH Keywords: monadic second-order logic
zbMATH Keywords: formal power series
MaRDI profile type: Publication
cites work: The logic of quantum mechanics
cites work: Determinization of weighted finite automata over strong bimonoids
cites work: Weighted automata and weighted logics
cites work: Weighted finite automata over strong bimonoids
cites work: Weighted automata and multi-valued logics over arbitrary bounded lattices
cites work: Weighted Logics for Nested Words and Algebraic Formal Power Series
cites work: Minimization algorithms for sequential transducers
cites work: Automata theory based on quantum logic: Some characterizations
cites work: Automata theory based on quantum logic: reversibilities and pushdown automata
cites work: On the definition of a family of automata
cites work: Automata theory based on quantum logic. I
cites work: A theory of computation based on quantum logic. I
Recommended article: Weighted Nested Word Automata and Logics over Strong Bimonoids
Recommended article: Weighted finite automata over strong bimonoids
Recommended article: Q4899894
Recommended article: Weighted automata and logics for infinite nested words
Recommended article: Determinization of weighted finite automata over strong bimonoids
Recommended article: The relationships among several forms of weighted finite automata over strong bimonoids
Recommended article: Automata, Languages and Programming
Recommended article: Weighted Automata and Weighted Logics
Recommended article: Weighted automata and weighted logics
title: Weighted nested word automata and logics over strong bimonoids
review text: A \textit{nested word} is formed of a finite word (on some alphabet \(\Delta\)) with a binary relation defining a nesting. More formally, a nested word is a finite word \(a_1\cdots a_n\) with a binary relation \(\nu\) on \(\{1,\dots,n\}\) such that \(i<j\) if \(\nu(i,j)\), \(\nu\) is a bijection between its projections on its first and second components and finally if \(\nu(i,j)\), \(\nu(i',j')\) and \(i<i'\) then either \(j<i'\) or \(j'<j\) (no overlapping).NEWLINENEWLINENested words are hence a representation for finite trees or functions calls. When \(\nu(i,j)\) holds, \(i\) is said to be a \textit{call} position and \(j\) a \textit{return} position. All other positions are said to be \textit{internal}.NEWLINENEWLINEThis notion was introduced in [\textit{R. Alur} and \textit{P. Madhusudan}, ``Adding nesting structure to words'', Lect. Notes Comput. Sci. 4036, 1--13 (2006; Zbl 1227.68045)], which furthermore defined a suitable notion of finite automata. Intuitively, this is the usual notion of finite automaton with the additional provision that on return positions the transition relation considers both the state at the return position and the state at the matching call position, in order to determine the next state.NEWLINENEWLINEThis paper generalizes nested word automata to bimonoids and gives a characterization of regular sets in terms of a monadic second-order logic.NEWLINENEWLINEA \textit{bimonoid} is a structure \((K,+,\cdot,0,1)\), where \(K\) is a set, \(+\) and \(\cdot\) are binary relations on \(K\) and \(0,1\in K\) such that \((K,+,0)\) and \((K,\cdot,1)\) are monoids. A bimonoid is said to be \textit{strong} if \(+\) is commutative and \(0\) acts as a multiplicative zero, i.e. \(k\cdot 0=0=0\cdot k\) for all \(k\in K\). A bimonoid \((K,+,\cdot,0,1)\) is said to be \textit{bi-locally finite} if both of the monoids \((K,+,0)\) and \((K,\cdot,1)\) are locally finite, i.e. their finitely generated submonoids are finite.NEWLINENEWLINENested automata are gene…
reviewed by: Roger Villemaire
description: scientific article; zbMATH DE number 6369423