.png){kind=icon}
.png){kind=icon}
Return
State-Freezing Pushdown Automata
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-02602-6_18.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Deterministic pushdown automata as well as deterministic one-counter automata with the restriction that their underlying state graph is quasi-acyclic are investigated. Here, quasi-acyclicity means that the graph is allowed to have self-loops, but removing the self-loops leads to an acyclic graph. Such automata are called state-freezing, since a state left can never be entered again. It turns out that the state-freezing property is a strong property, since the considered automata with the state-freezing property are less powerful than in the general case. This result holds in the real-time case, i.e., lambda-moves are not allowed, as well as in the case of allowed lambda-moves. We study the closure properties of the corresponding language families and can show that all families are anti-AFLs, whereas all families are closed under complementation. Finally, we look at decidability questions and obtain the undecidability of the inclusion problem already in the case of state-freezing real-time deterministic pushdown automata. However, the status of the inclusion problem in the case of state-freezing deterministic one-counter automata remains open.
Keywords:
Deterministic pushdown automata
Deterministic counter automata
Quasi-acyclic state graphs
State-Freezing
Computational capacity
Closure Properties
Decidability problems
Journal
I
IF:
0
Papers:
22
Citations:
0