ﻻ يوجد ملخص باللغة العربية
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
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
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
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
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