اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAn Extension of Parikhs Theorem beyond Idempotence
103
0
0.0
(
0
)
نشر من قبل
Michael Luttenberger
تاريخ النشر
2011
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The commutative ambiguity of a context-free grammar G assigns to each Parikh vector v the number of distinct leftmost derivations yielding a word with Parikh vector v. Based on the results on the generalization of Newtons method to omega-continuous semirings, we show how to approximate the commutative ambiguity by means of rational formal power series, and give a lower bound on the convergence speed of these approximations. From the latter result we deduce that the commutative ambiguity itself is rational modulo the generalized idempotence identity k=k+1 (for k some positive integer), and, subsequently, that it can be represented as a weighted sum of linear sets. This extends Parikhs well-known result that the commutative image of context-free languages is semilinear (k=1). Based on the well-known relationship between context-free grammars and algebraic systems over semirings, our results extend the work by Green et al. on the computation of the provenance of Datalog queries over commutative omega-continuous semirings.
قيم البحث
اقرأ أيضاً
Parikhs theorem states that the Parikh image of a context-free language is semilinear or, equivalently, that every context-free language has the same Parikh image as some regular language. We present a very simple construction that, given a context-f
ree grammar, produces a finite automaton recognizing such a regular language.
We provide a direct proof of Agafonovs theorem which states that finite state selection preserves normality. We also extends this result to the more general setting of shifts of finite type by defining selections which are compatible the shift. A sli
ghtly more general statement is obtained as we show that any Markov measure is preserved by finite state compatible selection.
Motivated by applications to stochastic differential equations, an extension of H{o}rmanders hypoellipticity theorem is proved for second-order degenerate elliptic operators with non-smooth coefficients. The main results are established using point-w
ise Bessel kernel estimates and a weighted Sobolev inequality of Stein and Weiss. Of particular interest is that our results apply to operators with quite general first-order terms.
A classical theorem of Herglotz states that a function $nmapsto r(n)$ from $mathbb Z$ into $mathbb C^{stimes s}$ is positive definite if and only there exists a $mathbb C^{stimes s}$-valued positive measure $dmu$ on $[0,2pi]$ such that $r(n)=int_0^{2
pi}e^{int}dmu(t)$for $nin mathbb Z$. We prove a quaternionic analogue of this result when the function is allowed to have a number of negative squares. A key tool in the argument is the theory of slice hyperholomorphic functions, and the representation of such functions which have a positive real part in the unit ball of the quaternions. We study in great detail the case of positive definite functions.
We analyse conformal gauge, or isotropic, singularities in cosmological models in general relativity. Using the calculus of tractors, we find conditions in terms of tractor curvature for a local extension of the conformal structure through a cosmolog
ical singularity and prove a local extension theorem.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
