Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userWreath Products of Distributive Forest Algebras
75
0
0.0
(
0
)
Added by
Michael Hahn
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 product 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 $varphi$ 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 events, 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
