<p>A generalized sequential machine (GSM) is a generalization of a Mealy machine where on each transition one input symbol is read and 0 or more output symbols are written. As in a Mealy machine, we assume that there are no final states, i.e. a GSM operates on infinite input/output words. A GSM has finitely many states.</p>

<p>Assume $A$ and $B$ are two single-valued GSMs and $C$ is a not necessarily single-valued GSM. Single-valued means that for each infinite input word there is at most one infinite output word (determinism is a sufficient but not necessary condition for single-valuedness). Suppose in addition that $A$ and $C$ are fully reachable, i.e. there is a path from the start state to every other state. In the following, two GSM synthesis problems are described. Let $T_X$ denote the set of states of GSM $X$.</p>

<ol>
<li>Are there single-valued GSMs $X$ and $Y$ such that $X \circ A \equiv Y \circ B$ and in $X \circ A$ for every $t \in T_A$ there is a state $(\_, t) \in T_X \times T_A$ reachable from the start state, i.e. $A$ remains fully reachable in $X \circ A$? Note that $\circ$ denotes transducer composition.</li>
<li>Are there single-valued, finite state transducers $X$ and $Y$ such that $X \circ C \supseteq Y \circ B$ and in $X \circ C$ for every $t \in T_C$ there is a state $(\_, t) \in T_X \times T_C$ reachable from the start state, i.e. $C$ remains fully reachable in $X \circ C$?</li>
</ol>

<p>Clearly, 1. is semi-decidable and 2. is undecidable if $C$ is non-deterministic (without restriction, i.e. infinitely-valued). However, is 1. decidable and if so what is the complexity? For it to be decidable it must be possible to bound the number of states of $X$ and $Y$. Moreover, is 2. decidable if $C$ is finitely-valued, i.e. there is a bounded number of infinite output words for each infinite input word? I'm particularly interested in symbolic methods, also references to practical bounded synthesis approaches. I appreciate any hints that relate this problem to a standard problem as well. Thanks for your input.</p>

CC BY-SA 3.0
2014-01-02T19:31:12.647Z
idea, can this be simplified/converted to a problem where all the input/output alphabets are the same?
vzn
CC BY-SA 3.0
2014-01-02T23:00:26.077Z
@vzn: Good point. I don't see a problem when we assume that all $\Sigma_\_$ and $\Gamma_\_$ are equal. I just added the details to provide an intuition of $X$ and $Y$. Moreover, in 1. we can replace $B \circ C$ by some single-valued finite state transducer $D$.
Dave Lang
CC BY-SA 3.0
2014-01-03T03:38:25.533Z
re ref to infinite words, are these actually something like buchi transducers?
vzn
CC BY-SA 3.0
2014-01-03T12:35:12.790Z
@vzn: Thanks for your question. I extended my post. The transducer considered here has no final states. The automaton transduces (input, output) words $(u, v) \in (\Sigma^\star \cup \Sigma^\omega) \times (\Gamma^\star \cup \Gamma^\omega)$, i.e. both finite and infinite words (due to $\epsilon$ transitions). However, it's also fine to assume a generalized sequential machine without final states instead (must consume an input symbol on each transition).
Dave Lang
CC BY-SA 3.0
2014-01-03T12:45:36.973Z
An input/output word $(u, v)$ is transduced if there is a corresponding path in the transducer. There are no acceptance conditions as in Büchi or Muller automata.
Dave Lang
CC BY-SA 3.0
2014-01-03T17:41:33.920Z
all input/output words are finite in std FSM transducers. maybe you meant "unbounded length". buchi automata do in fact have an acceptance concept related to patterns/recurrences in infinite words.
vzn
CC BY-SA 3.0
2014-01-04T00:09:31.363Z
@vzn: Yes, you are right. This is why I should have mentioned it. You can think of the transducer here as a generalized sequential machine which itself is a generalization of a Mealy machine by allowing output words in $\Gamma^\star$ on a transition. The transducer I had in mind when writing the post is a generalization of a generalized sequential machine by allowing $\epsilon$ input words on a transition as well. In any case, there are no final states, i.e. the automata process infinite words.
Dave Lang
CC BY-SA 3.0
2014-01-04T01:33:38.873Z
I rewrote the post now replacing "transducer" by "generalized sequential machine" and taking out some technicalities which are of no importance. 2. is slightly changed compared to the previous version as now reachability must hold for a not necessarily single-valued automaton whereas before it had to hold for a single-valued automaton.
Dave Lang
CC BY-SA 3.0
2014-01-04T04:08:56.367Z
still think the ref to "each infinite input word" is not quite right. however superficially there is some similarity to this question asking about [self similar transducer homomorphisms](http://cstheory.stackexchange.com/questions/19280/finding-self-similar-homomorphisms-of-a-fsm-transducer) where a homomorphism can be seen as a special case of a transducer. the theory seems not to cover too much q's in form "create/construct transducer $X$ such that..." other than compositions; but have some further ideas, how about continuing in [chat](http://chat.stackexchange.com/rooms/9446/theory-salon)
vzn
CC BY-SA 3.0
2014-01-05T08:00:27.137Z
Isn't the definition of composition a bit problematic if a transducer can output multiple letters? Semantically it is still OK: $(u,w)\in X\circ A$ if there is a $v$ such that $(u,v)\in X$ and $(v,w)\in A$. But what is the canonical _construction_ of $X\circ A$? Suppose $A$ is the identity, but has two states $s_0$ and $s_1$: input bit $b$ takes it to state $s_b$. Also, $X$ has one state and no matter the input it outputs $10$. What is the composition $X\circ A$? Are the states of $A$ "reachable in the composition"?
Radu GRIGore
CC BY-SA 3.0
2014-01-06T13:02:08.977Z
@RaduGRIGore: For any state in $X \times A$, you follow multiple transitions according to output of the $X$-transition. In your example, you obtain an automaton with one "symbolic" transition $(s_X, s_0) \rightarrow (s_X, s_1)$ labeled with any $X$ input symbol and output 01 and another "symbolic" transition $(s_X, s_1) \rightarrow (s_X, s_1)$ labeled with any $X$ input symbol and output 01. The states of $A$ are reachable in the composition.
Dave Lang
<cc.complexity-theory><ds.algorithms><lo.logic><automata-theory><sat>
Generalized sequential machine synthesis subject to language equivalence/inclusion and reachability
Dave Lang
# Generalized sequential machine synthesis subject to language equivalence/inclusion and reachability

(Asked by: username_0 on 2014-01-01)

A generalized sequential machine (GSM) is a generalization of a Mealy machine where on each transition one input symbol is read and 0 or more output symbols are written. As in a Mealy machine, we assume that there are no final states, i.e. a GSM operates on infinite input/output words. A GSM has finitely many states.

Assume $A$ and $B$ are two single-valued GSMs and $C$ is a not necessarily single-valued GSM. Single-valued means that for each infinite input word there is at most one infinite output word (determinism is a sufficient but not necessary condition for single-valuedness). Suppose in addition that $A$ and $C$ are fully reachable, i.e. there is a path from the start state to every other state. In the following, two GSM synthesis problems are described. Let $T\_X$ denote the set of states of GSM $X$.

1. Are there single-valued GSMs $X$ and $Y$ such that $X \circ A \equiv Y \circ B$ and in $X \circ A$ for every $t \in T\_A$ there is a state $(\\_, t) \in T\_X \times T\_A$ reachable from the start state, i.e. $A$ remains fully reachable in $X \circ A$? Note that $\circ$ denotes transducer composition.
2. Are there single-valued, finite state transducers $X$ and $Y$ such that $X \circ C \supseteq Y \circ B$ and in $X \circ C$ for every $t \in T\_C$ there is a state $(\\_, t) \in T\_X \times T\_C$ reachable from the start state, i.e. $C$ remains fully reachable in $X \circ C$?

Clearly, 1. is semi-decidable and 2. is undecidable if $C$ is non-deterministic (without restriction, i.e. infinitely-valued). However, is 1. decidable and if so what is the complexity? For it to be decidable it must be possible to bound the number of states of $X$ and $Y$. Moreover, is 2. decidable if $C$ is finitely-valued, i.e. there is a bounded number of infinite output words for each infinite input word? I'm particularly interested in symbolic methods, also references to practical bounded synthesis approaches. I appreciate any hints that relate this problem to a standard problem as well. Thanks for your input.

**Tags:** cc.complexity-theory, ds.algorithms, lo.logic, automata-theory, sat
> **Comments:**
> **username_1**: idea, can this be simplified/converted to a problem where all the input/output alphabets are the same?  
> **username_0**: @vzn: Good point. I don't see a problem when we assume that all $\Sigma_\_$ and $\Gamma_\_$ are equal. I just added the details to provide an intuition of $X$ and $Y$. Moreover, in 1. we can replace $B \circ C$ by some single-valued finite state transducer $D$.  
> **username_1**: re ref to infinite words, are these actually something like buchi transducers?  
> **username_0**: @vzn: Thanks for your question. I extended my post. The transducer considered here has no final states. The automaton transduces (input, output) words $(u, v) \in (\Sigma^\star \cup \Sigma^\omega) \times (\Gamma^\star \cup \Gamma^\omega)$, i.e. both finite and infinite words (due to $\epsilon$ transitions). However, it's also fine to assume a generalized sequential machine without final states instead (must consume an input symbol on each transition).  
> **username_0**: An input/output word $(u, v)$ is transduced if there is a corresponding path in the transducer. There are no acceptance conditions as in Büchi or Muller automata.  
> **username_1**: all input/output words are finite in std FSM transducers. maybe you meant "unbounded length". buchi automata do in fact have an acceptance concept related to patterns/recurrences in infinite words.  
> **username_0**: @vzn: Yes, you are right. This is why I should have mentioned it. You can think of the transducer here as a generalized sequential machine which itself is a generalization of a Mealy machine by allowing output words in $\Gamma^\star$ on a transition. The transducer I had in mind when writing the post is a generalization of a generalized sequential machine by allowing $\epsilon$ input words on a transition as well. In any case, there are no final states, i.e. the automata process infinite words.  
> **username_0**: I rewrote the post now replacing "transducer" by "generalized sequential machine" and taking out some technicalities which are of no importance. 2. is slightly changed compared to the previous version as now reachability must hold for a not necessarily single-valued automaton whereas before it had to hold for a single-valued automaton.  
> **username_1**: still think the ref to "each infinite input word" is not quite right. however superficially there is some similarity to this question asking about [self similar transducer homomorphisms](http://cstheory.stackexchange.com/questions/19280/finding-self-similar-homomorphisms-of-a-fsm-transducer) where a homomorphism can be seen as a special case of a transducer. the theory seems not to cover too much q's in form "create/construct transducer $X$ such that..." other than compositions; but have some further ideas, how about continuing in [chat](http://chat.stackexchange.com/rooms/9446/theory-salon)  
> **username_2**: Isn't the definition of composition a bit problematic if a transducer can output multiple letters? Semantically it is still OK: $(u,w)\in X\circ A$ if there is a $v$ such that $(u,v)\in X$ and $(v,w)\in A$. But what is the canonical _construction_ of $X\circ A$? Suppose $A$ is the identity, but has two states $s_0$ and $s_1$: input bit $b$ takes it to state $s_b$. Also, $X$ has one state and no matter the input it outputs $10$. What is the composition $X\circ A$? Are the states of $A$ "reachable in the composition"?  
> **username_0**: @RaduGRIGore: For any state in $X \times A$, you follow multiple transitions according to output of the $X$-transition. In your example, you obtain an automaton with one "symbolic" transition $(s_X, s_0) \rightarrow (s_X, s_1)$ labeled with any $X$ input symbol and output 01 and another "symbolic" transition $(s_X, s_1) \rightarrow (s_X, s_1)$ labeled with any $X$ input symbol and output 01. The states of $A$ are reachable in the composition.  

---

## 0 answers

