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

lmcs:854 - Logical Methods in Computer Science, February 19, 2010, Volume 6, Issue 1 - https://doi.org/10.2168/LMCS-6(1:5)2010
Weighted Logics for Nested Words and Algebraic Formal Power Series

Authors: Christian Mathissen

    Nested words, a model for recursive programs proposed by Alur and Madhusudan, have recently gained much interest. In this paper we introduce quantitative extensions and study nested word series which assign to nested words elements of a semiring. We show that regular nested word series coincide with series definable in weighted logics as introduced by Droste and Gastin. For this we establish a connection between nested words and the free bisemigroup. Applying our result, we obtain characterizations of algebraic formal power series in terms of weighted logics. This generalizes results of Lautemann, Schwentick and Therien on context-free languages.


    Volume: Volume 6, Issue 1
    Published on: February 19, 2010
    Accepted on: June 25, 2015
    Submitted on: December 8, 2008
    Keywords: Computer Science - Logic in Computer Science,F.1.1,F.1.2,F.4.1,F.4.3

    7 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 322 times.
    This article's PDF has been downloaded 253 times.