اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA Language Hierarchy of Binary Relations
301
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Motivated by the study of word problems of monoids, we explore two ways of viewing binary relations on $A^*$ as languages. We exhibit a hierarchy of classes of binary relations on $A^*$, according to the class of languages the relation belongs to and the chosen viewpoint. We give examples of word problems of monoids distinguishing the various classes.
قيم البحث
اقرأ أيضاً
Antonenko and Russyev independently have shown that any Mealy automaton with no cycles with exit--that is, where every cycle in the underlying directed graph is a sink component--generates a fi- nite (semi)group, regardless of the choice of the produ
ction functions. Antonenko has proved that this constitutes a characterization in the non-invertible case and asked for the invertible case, which is proved in this paper.
Given a pseudoword over suitable pseudovarieties, we associate to it a labeled linear order determined by the factorizations of the pseudoword. We show that, in the case of the pseudovariety of aperiodic finite semigroups, the pseudoword can be recovered from the labeled linear order.
The simplest example of an infinite Burnside group arises in the class of automaton groups. However there is no known example of such a group generated by a reversible Mealy automaton. It has been proved that, for a connected automaton of size at mos
t~3, or when the automaton is not bireversible, the generated group cannot be Burnside infinite. In this paper, we extend these results to automata with bigger stateset, proving that, if a connected reversible automaton has a prime number of states, it cannot generate an infinite Burnside group.
We revisit here congruence relations for Buchi automata, which play a central role in the automata-based verification. The size of the classical congruence relation is in $3^{mathcal{O}(n^2)}$, where $n$ is the number of states of a given Buchi autom
aton $mathcal{A}$. Here we present improved congruence relations that can be exponentially coarser than the classical one. We further give asymptotically optimal congruence relations of size $2^{mathcal{O}(n log n)}$. Based on these optimal congruence relations, we obtain an optimal translation from Buchi automata to a family of deterministic finite automata (FDFW) that accepts the complementary language. To the best of our knowledge, our construction is the first direct and optimal translation from Buchi automata to FDFWs.
In this paper we introduce a novel, context-free grammar, {it RNAFeatures$^*$}, capable of generating any RNA structure including pseudoknot structures (pk-structure). We represent pk-structures as orientable fatgraphs, which naturally leads to a fil
tration by their topological genus. Within this framework, RNA secondary structures correspond to pk-structures of genus zero. {it RNAFeatures$^*$} acts on formal, arc-labeled RNA secondary structures, called $lambda$-structures. $lambda$-structures correspond one-to-one to pk-structures together with some additional information. This information consists of the specific rearrangement of the backbone, by which a pk-structure can be made cross-free. {it RNAFeatures$^*$} is an extension of the grammar for secondary structures and employs an enhancement by labelings of the symbols as well as the production rules. We discuss how to use {it RNAFeatures$^*$} to obtain a stochastic context-free grammar for pk-structures, using data of RNA sequences and structures. The induced grammar facilitates fast Boltzmann sampling and statistical analysis. As a first application, we present an $O(n log(n))$ runtime algorithm which samples pk-structures based on ninety tRNA sequences and structures from the Nucleic Acid Database (NDB).
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
