Paper Info

Title | ||
---|---|---|

Iterated linear control and iterated one-turn pushdowns |

Abstract | ||
---|---|---|

For a classL of languages, anL-controlled linear grammarK consists of a linear context-free grammarG and a control languageH inL, where the terminals ofH are interpreted as the labels of rules ofG. The language generated byK is obtained by derivations ofG such that the corresponding strings of labels of the rules applied are control strings inH. The control of linear grammars can be iterated by starting withL and by taking the result of thekth step as class of control languages for the (k + 1)st step. The language class obtained by thekth step is denoted by CTRLk(L). Denote byL(S) the language class accepted by nondeterministic one-wayS automata, whereS is a storage type. We prove that for anyS, CTRLk(L(S)) = L(P1tk(S)), whereP1tk(S) is the storage type the configurations of which consist ofk-iterated one-turn pushdowns ofS-configurations. We establish a strong connection between iterated linear control and iterated one-turn pushdowns. In particular, we characterize CTRLk(LCF), where LCF is the class of context-free languages, by iterated one-turn pushdown automata in which the innermost pushdown is unrestricted. |

Year | DOI | Venue |
---|---|---|

1986 | 10.1007/BFb0028831 | Mathematical Systems Theory |

Keywords | Field | DocType |

Computational Mathematic,Strong Connection,Linear Control,Language Class,Control String | Rule-based machine translation,Discrete mathematics,Combinatorics,Context-free language,Nondeterministic algorithm,Automaton,Pushdown automaton,Iterated function,Linear control,Mathematics | Journal |

Volume | Issue | ISBN |

19 | 2 | 3-540-15689-5 |

Citations | PageRank | References |

14 | 1.44 | 23 |

Authors | ||

1 |

Authors (1 rows)

Cited by (14 rows)

References (23 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Heiko Vogler | 1 | 612 | 43.44 |