| 1. |
- Bensch, Suna, et al.
(author)
-
Deterministic Stack Transducers
- 2016
-
In: Implementation and Application of Automata. - Cham : Springer. - 9783319409450 - 9783319409467 ; , s. 27-38
-
Conference paper (peer-reviewed)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.
|
|
| 2. |
- Bensch, Suna, et al.
(author)
-
Deterministic Stack Transducers
- 2017
-
In: International Journal of Foundations of Computer Science. - : World Scientific Publishing Co. Pte. Ltd.. - 0129-0541. ; 28:5, s. 583-601
-
Journal article (peer-reviewed)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.
|
|
| 3. |
- Bensch, Suna, et al.
(author)
-
Extended Uniformly Limited T0L Languages and Mild Context-Sensitivity
- 2016
-
In: Eight Workshop on Non-Classical Models of Automata and Applications (NCMA 2016). - Wien : Institut für Computersprachen. - 9783200047259 ; , s. 35-46
-
Conference paper (peer-reviewed)abstract
- We study the fixed membership problem for k-uniformly-limited and propagating ET0L systems (kulEPT0L systems). To this end, the algorithm given in [7] is applied. It follows that kulEPT0L languages are parsable in polynomial time. Since kulEPT0L languages are semi-linear [1] and kulEPT0L systems generate certain non-context-free languages, which capture the non-context-free phenomena occurring in natural languages, this is the last building block to show that kulEPT0L languages, for k ≥ 2, belong to the family of mildly context-sensitive languages.
|
|
| 4. |
- Bensch, Suna, et al.
(author)
-
Input-driven stack automata
- 2012
-
In: Theoretical computer science. - Berlin, Heidelberg : Springer Nature. - 9783642334740 - 9783642334757 ; , s. 28-42
-
Conference paper (peer-reviewed)abstract
- We introduce and investigate input-driven stack automata, which are a generalization of input-driven pushdown automata that recently became popular under the name visibly pushdown automata. Basically, the idea is that the input letters uniquely determine the operations on the pushdown store. This can nicely be generalized to stack automata by further types of input letters which are responsible for moving the stack pointer up or down. While visibly pushdown languages share many desirable properties with regular languages, input-driven stack automata languages do not necessarily so. We prove that deterministic and non- deterministic input-driven stack automata have different computational power, which shows in passing that one cannot construct a deterministic input-driven stack automaton from a nondeterministic one. We study the computational capacity of these devices. Moreover, it is shown that the membership problem for nondeterministic input-driven stack automata languages is NP-complete.
|
|
| 5. |
- Bensch, Suna, et al.
(author)
-
On input-revolving deterministic and nondeterministic finite automata
- 2009
-
In: Information and Computation. - 0890-5401 .- 1090-2651. ; 207, s. 1140-1155
-
Journal article (peer-reviewed)abstract
- We introduce and investigate input-revolving finite automata, which are (nondeterministic) finite state automata with additional ability to shift the remaining part of the input. Three different modes of shifting are considered, namely revolving to the left, revolving to the right, and circular-interchanging. We investigate the computational capacities of these three types of automata and their deterministic variants, comparing any of the six classes of automata with each other and with further classes of well-known automata. In particular, it is shown that nondeterminism is better than determinism, that is, for all three modes of shifting there is a language accepted by the nondeterministic model but not accepted by any determinstic automaton of the same type. Concerning the closure properties most of the deterministic language families studied are not closed under standard operations. For example, we show that the family of languages accepted by deterministic right-revolving finite automata is an anti-AFL which is not closed under reversal and intersection.
|
|
