0
$\begingroup$

Assume we have two LTSs, say DFA with labels over the transitions (though the question can be generalized to more sophisticated automatons), define the input to each system to be as usual just the input word, and define the output of each system to be the sequence of labels of visited transitions.

Now assume that the two systems are wired directly to each other: every output letter (i.e. non-epsilon transition) in system A becomes instantly an input letter to system B, and output of B becomes input of A.

I'm looking for some analysis of this construction. Maybe anyone happen to be familiar with research topic that discuss such?

EDIT: Special case - if we have labelled pushdown automatons (context free grammars), then is the combined system as powerful as a two-pushdown machine (Turing powerful)? Or is strictly weaker?

$\endgroup$
  • 2
    $\begingroup$ If you combine two DFAs this way, then you can simulate the combined system using another DFA. $\endgroup$ – Yuval Filmus Dec 2 '16 at 16:20
  • $\begingroup$ thanks, any clue or reference please? :) $\endgroup$ – Troy McClure Dec 2 '16 at 16:27
  • 1
    $\begingroup$ Your definition is a little problematic. If say A has twenty transitions and we want to read all these in B we need at least twenty transitions for B. And vice versa. That means the transitions are in one-to-one correspondence? I however you allow general output labels then the situation drastically changes, and you can do horrendous things. $\endgroup$ – Hendrik Jan Dec 2 '16 at 17:09
  • 1
    $\begingroup$ 1. I don't think I understand your definition. Each transition is labelled with a single symbol from $\Sigma$? If so, for any single LTS, isn't the output always exactly equal to the input? It seems like it would help if you set up the problem a bit more precisely. $\endgroup$ – D.W. Dec 2 '16 at 17:36
  • 1
    $\begingroup$ You say: "the output of each system to be the sequence of labels of visited transitions". So every transition has exactly one output label? Epsilon transitions are transitions that read nothing (as opposed to output nothing). What can be input/output? If they are arbitrary labels (instead of transitions) then (again) they are very powerful, even without push-downs. $\endgroup$ – Hendrik Jan Dec 2 '16 at 17:41
2
$\begingroup$

Transducers, or finite automata with output, are very powerful when they can be iterated. After all a step of a Turing machine on a tape (or better a instantaneous description, with the state assumed to be marked on the tape) is just a simple local rewrite, and iterating that is a computation.

With two transducers $T_M$ and $T_e$ we can mimick that iteration. Assume $T_e$ just echos what it reads. $T_M$ starts on empty input by writing the initial configuration and marker $\#w_0$, which it then gets as input via $T_e$. Then $T_M$ computes the next configuration of TM $M$ and writes $\#w_2$, etcetera. In that way $T_M$ writes a complete computation of $M$ in the form $\#w_1\#w_2\#w_3\dots$. If TM $M$ cleans its tape before halting, and if $T_M$ stops (and accepts) when it reads empty tape with halting state of $M$, the system has a halting computation iff the TM has one. Quite powerful.

In a simpler example $T$ gets a string $a^n\#$ as input. If $n$ is even it halves $n$ and outputs $a^{n/2}\#$, if $n$ is odd $T$ blocks (halts in a negative state, or runs off in a never halting sequence of epsilon moves), except when $n$ equals $1$, then it will accept and halt. Observe that when the output if $T$ is fed back as input, the system will only halt when the initial value of $n$ was a power of two.

In fact, what is obtained is a so-called fixed point language of the transducer $T$: strings $w$ such that $T$ writes $T$ on input $w$. If I recall well, the fixed point languages of `rational functions' (finite state transducers that are not necessarily deterministic, but have only one output on a given string) are co-context-free, complements of context-free languages. Prefix and equality languages of rational functions are co-context-free, Information Processing Letters, 1988, doi:10.1016/0020-0190(88)90167-6,

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.