Questions tagged [transducers]
The transducers tag has no usage guidance.
12
questions with no upvoted or accepted answers
3
votes
0answers
52 views
How to apply insights from the theory of codes to alternating codes?
The book Theory of codes by J. Berstel and D. Perrin from 1985 studies variable-length codes. The focus is less on error-correction and compression, but more on algebraic properties, synchronization ...
2
votes
0answers
26 views
Regular string relations - proof of correctness
Let $T \subseteq \Sigma^* \times \Sigma^*$ be a regular (rational) relation. We define the obligatory rewrite relation over $T$ as follows:
$$
R^{obl}(T) := N(T) \cdot (T \cdot N(T))^*
$$
$$
N(T) := ...
2
votes
0answers
94 views
Which transducer models replacement in regex?
I am looking for the right transducer which allows to translate a sequence of literals into a sequence of same literals (or a subset of them) in arbitrary order.
For example: ABC => CAB, which, with ...
1
vote
0answers
19 views
Chomsky hierarchy for finite state transducers
In this question in the first answer someone mentions a "special transduction hierarchy". I cannot find anywhere anything about it. Could someone point me to resources on this topic?
1
vote
0answers
197 views
Regexp substitution and finite-state transducers
Many programming languages support a "regular expression substitution" operation: if r is a regular expression and s, ...
1
vote
0answers
27 views
almost realtime push down relation vs realtime pushdown relation?
Almost realtime pushdown relation pop a symbol for each empty step.
Realtime pushdown relation does not perform any empty step.
What do they mean by empty step?
0
votes
0answers
21 views
About quasi-linear finite automata
Let M a finite state transducer define as : $M=<X,Y,S,\delta,\lambda>$
What we mean by quasi-linear finite automata?
0
votes
0answers
17 views
Mealy machine and moore machine
Can we compute the number of machine of two kind of transducers (mealy and moore) with $n$ states, and lenght of input symbols $m$, and lenght of output symbols $p$.
0
votes
0answers
18 views
About number of NFSTs
Can we proof the number of NFSTs with $n$ states : $n.2^{mpn}.2^{n}$ where $p$ is the cardinal of input alphabet and $m$ the cardinal of output alphabet.
0
votes
0answers
23 views
What is the optimal combination of transducers with limited capabilities to a more powerful transducer?
Assume we have a number of transducers with limited information processing capabilities. Are there theoretical results (proofs) on how these transducers can be combined by some sort of communication ...
0
votes
0answers
35 views
Are polynomials in one variable logspace-computable?
Given a polynomial function
$$p\quad=\quad \lambda\, x\in\mathbb{N}_0.\ \sum_{i=0}^n a_i x^i$$
with $a_i\in\mathbb{Z}$ for all $i\leqslant n$, can you compute $p$ by a logspace transducer if the input ...
-3
votes
1answer
98 views
State machine that multiplies a binary number with a constant
I'm trying to create a FSM that multiplies a bitstream with a constant value (e.g 3).
I don't have a clue how to design such a FSM. Any hints?
