اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدWreath Products of Distributive Forest Algebras
75
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
It is an open problem whether definability in Propositional Dynamic Logic (PDL) on forests is decidable. Based on an algebraic characterization by Bojanczyk, et. al.,(2012) in terms of forest algebras, Straubing (2013) described an approach to PDL based on a k-fold iterated distributive law. A proof that all languages satisfying such a k-fold iterated distributive law are in PDL would settle decidability of PDL. We solve this problem in the case k=2: All languages recognized by forest algebras satisfying a 2-fold iterated distributive law are in PDL. Furthermore, we show that this class is decidable. This provides a novel nontrivial decidable subclass of PDL, and demonstrates the viability of the proposed approach to deciding PDL in general.
قيم البحث
اقرأ أيضاً
We develop a new algebraic framework to reason about languages of Mazurkiewicz traces. This framework supports true concurrency and provides a non-trivial generalization of the wreath product operation to the trace setting. A novel local wreath produ
ct principle has been established. The new framework is crucially used to propose a decomposition result for recognizable trace languages, which is an analogue of the Krohn-Rhodes theorem. We prove this decomposition result in the special case of acyclic architectures and apply it to extend Kamps theorem to this setting. We also introduce and analyze distributed automata-theoretic operations called local and global cascade products. Finally, we show that aperiodic trace languages can be characterized using global cascade products of localized and distributed two-state reset automata.
We develop a theory of semidirect products of partial groups and localities. Our concepts generalize the notions of direct products of partial groups and localities, and of semidirect products of groups.
Let $varphi: {mathbb P}^1 longrightarrow {mathbb P}^1$ be a rational map of degree greater than one defined over a number field $k$. For each prime ${mathfrak p}$ of good reduction for $varphi$, we let $varphi_{mathfrak p}$ denote the reduction of $v
arphi$ modulo ${mathfrak p}$. A random map heuristic suggests that for large ${mathfrak p}$, the proportion of periodic points of $varphi_{mathfrak p}$ in ${mathbb P}^1({mathfrak o}_k/{mathfrak p})$ should be small. We show that this is indeed the case for many rational functions $varphi$.
We develop new algebraic tools to reason about concurrent behaviours modelled as languages of Mazurkiewicz traces and asynchronous automata. These tools reflect the distributed nature of traces and the underlying causality and concurrency between eve
nts, and can be said to support true concurrency. They generalize the tools that have been so efficient in understanding, classifying and reasoning about word languages. In particular, we introduce an asynchronous version of the wreath product operation and we describe the trace languages recognized by such products (the so-called asynchronous wreath product principle). We then propose a decomposition result for recognizable trace languages, analogous to the Krohn-Rhodes theorem, and we prove this decomposition result in the special case of acyclic architectures. Finally, we introduce and analyze two distributed automata-theoretic operations. One, the local cascade product, is a direct implementation of the asynchronous wreath product operation. The other, global cascade sequences, although conceptually and operationally similar to the local cascade product, translates to a more complex asynchronous implementation which uses the gossip automaton of Mukund and Sohoni. This leads to interesting applications to the characterization of trace languages definable in first-order logic: they are accepted by a restricted local cascade product of the gossip automaton and 2-state asynchronous reset automata, and also by a global cascade sequence of 2-state asynchronous reset automata. Over distributed alphabets for which the asynchronous Krohn-Rhodes theorem holds, a local cascade product of such automata is sufficient and this, in turn, leads to the identification of a simple temporal logic which is expressively complete for such alphabets.
Let $m$ be a positive integer and let $Omega$ be a finite set. The $m$-closure of $Gle$Sym$(Omega)$ is the largest permutation group on $Omega$ having the same orbits as $G$ in its induced action on the Cartesian product $Omega^m$. The exact formula
for the $m$-closure of the wreath product in product action is given. As a corollary, a sufficient condition is obtained for this $m$-closure to be included in the wreath product of the $m$-closures of the factors.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
