2016/09/13 by Manfred Droste, George Rahonis
Computer Science · #Advanced Algebra and Logic #Atomic formula #Characterization (materials science) #Decidability #Equivalence (formal languages) #Exponential function #Fragment (logic) #Linear logic #Linear temporal logic #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #cs.LO
paper · pdf · doi:10.4204/eptcs.226.11
published as EPTCS 226, 2016, pp. 149-163 · In Proceedings GandALF 2016, arXiv:1609.03648
openalex publication_date 2016/09/13 · arxiv created 2016/09/14 · arxiv updated 2016/09/15 · openalex created_date 2016/09/23 · openalex updated_date 2026/08/06
We introduce a weighted linear dynamic logic (weighted LDL for short) and show the expressive equivalence of its formulas to weighted rational expressions. This adds a new characterization for recognizable series to the fundamental Sch"utzenberger theorem. Surprisingly, the equivalence does not require any restriction to our weighted LDL. Our results hold over arbitrary (resp. totally complete) semirings for finite (resp. infinite) words. As a consequence, the equivalence problem for weighted LDL formulas over fields is decidable in doubly exponential time. In contrast to classical logics, we show that our weighted LDL is expressively incomparable to weighted LTL for finite words. We determine a fragment of the weighted LTL such that series over finite and infinite words definable by LTL formulas in this fragment are definable also by weighted LDL formulas.