Name
Abstract | ||
|---|---|---|
We introduce and investigate stack transducers, which are one-way stack automata with an output tape. A one-way stack automaton is a classical pushdown automaton with the additional ability to move the stack head inside the stack without altering the contents. For stack transducers, we distinguish between a digging and a non-digging mode. In digging mode, the stack transducer can write on the output tape when its stack head is inside the stack, whereas in non-digging mode, the stack transducer is only allowed to emit symbols when its stack head is at the top of the stack. These stack transducers have a motivation from natural language interface applications, as they capture long-distance dependencies in syntactic, semantic, and discourse structures. We study the computational capacity for deterministic digging and non-digging stack transducers, as well as for their non-erasing and checking versions. We finally show that even for the strongest variant of stack transducers the stack languages are regular. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-319-40946-7_3 | IMPLEMENTATION AND APPLICATION OF AUTOMATA |
DocType | Volume | Issue |
Journal | 9705 | 5 |
ISSN | Citations | PageRank |
0302-9743 | 2 | 0.40 |
References | Authors | |
9 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Suna Bensch | 1 | 42 | 14.67 |
| Johanna Björklund | 2 | 5 | 6.23 |
| Martin Kutrib | 3 | 778 | 89.77 |