Weighted Logics for Nested Words and Algebraic Formal Power Series

Details Weighted Logics for Nested Words and Algebraic Formal Power Series Weighted Logics for Nested Words and Algebraic Formal Power Series

2010-01-13

arxiv.org/abs/1001.2175v2

LMCS 6 (1:5) 2010

Computer Science

Logic in Computer Science

Scientific paper

10.2168/LMCS-6(1:5)2010

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.

Affiliated with

Also associated with

No associations

Rating

Weighted Logics for Nested Words and Algebraic Formal Power Series does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Weighted Logics for Nested Words and Algebraic Formal Power Series, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Weighted Logics for Nested Words and Algebraic Formal Power Series will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-525416