ترغب بنشر مسار تعليمي؟ اضغط هنا

On the Balancedness of Tree-to-word Transducers

63   0   0.0 ( 0 )
 نشر من قبل Raphaela L\\\"obel
 تاريخ النشر 2019
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

A language over an alphabet $B = A cup overline{A}$ of opening ($A$) and closing ($overline{A}$) brackets, is balanced if it is a subset of the Dyck language $D_B$ over $B$, and it is well-formed if all words are prefixes of words in $D_B$. We show that well-formedness of a context-free language is decidable in polynomial time, and that the longest common reduced suffix can be computed in polynomial time. With this at a hand we decide for the class 2-TWs of non-linear tree transducers with output alphabet $B^*$ whether or not the output language is balanced.



قيم البحث

اقرأ أيضاً

We show that equivalence of deterministic linear tree transducers can be decided in polynomial time when their outputs are interpreted over the free group. Due to the cancellation properties offered by the free group, the required constructions are n ot only more general, but also simpler than the corresponding constructions for proving equivalence of deterministic linear tree-to-word transducers.
We consider input-deterministic finite state transducers with infinite inputs and infinite outputs, and we consider the property of Borel normality on infinite words. When these transducers are given by a strongly connected set of states, and when th e input is a Borel normal sequence, the output is an infinite word such that every word has a frequency given by a weighted automaton over the rationals. We prove that there is an algorithm that decides in cubic time whether an input-deterministic transducer preserves normality.
58 - Olivier Carton 2020
We consider finite state non-deterministic but unambiguous transducers with infinite inputs and infinite outputs, and we consider the property of Borel normality of sequences of symbols. When these transducers are strongly connected, and when the inp ut is a Borel normal sequence, the output is a sequence in which every block has a frequency given by a weighted automaton over the rationals. We provide an algorithm that decides in cubic time whether a unambiguous transducer preserves normality.
Deterministic two-way transducers on finite words have been shown by Engelfriet and Hoogeboom to have the same expressive power as MSO-transductions. We introduce a notion of aperiodicity for these transducers and we show that aperiodic transducers c orrespond exactly to FO-transductions. This lifts to transducers the classical equivalence for languages between FO-definability, recognition by aperiodic monoids and acceptance by counter-free automata.
We present Woorpje, a string solver for bounded word equations (i.e., equations where the length of each variable is upper bounded by a given integer). Our algorithm works by reformulating the satisfiability of bounded word equations as a reachabilit y problem for nondeterministic finite automata, and then carefully encoding this as a propositional satisfiability problem, which we then solve using the well-known Glucose SAT-solver. This approach has the advantage of allowing for the natural inclusion of additional linear length constraints. Our solver obtains reliable and competitive results and, remarkably, discovered several cases where state-of-the-art solvers exhibit a faulty behaviour.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا