Indécidabilité de la condition IRS
Autebert, Jean-Michel ; Beauquier, Joffroy ; Boasson, Luc ; Latteux, Michel
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 16 (1982), p. 129-138 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1982-01-01
@article{ITA_1982__16_2_129_0,
     author = {Autebert, Jean-Michel and Beauquier, Joffroy and Boasson, Luc and Latteux, Michel},
     title = {Ind\'ecidabilit\'e de la condition IRS},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {16},
     year = {1982},
     pages = {129-138},
     mrnumber = {674924},
     zbl = {0493.68075},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/ITA_1982__16_2_129_0}
}

Autebert, Jean-Michel; Beauquier, Joffroy; Boasson, Luc; Latteux, Michel. Indécidabilité de la condition IRS. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 16 (1982) pp. 129-138. http://gdmltest.u-ga.fr/item/ITA_1982__16_2_129_0/

1.J. M. Autebert, G. Cousineau etM. Nivat, Les Langages Algébriques, Hermann, Paris (à paraître).

2. L. Boasson, Un LangageAlgébrique Particulier, R.A.I.R.O., Informatique théorique, vol. 13, 1979, p. 203-215. | Numdam | MR 554682 | Zbl 0424.68042

4. E. Friedmann, The Inclusion Problem for Simple Languages, Theoretical Computer Science, vol. 1, 1976, p. 297-316. | MR 405936 | Zbl 0349.68032

5. C. Frougny, Langages très Simples Générateurs, R.A.I.R.O., Informatique Théorique, vol. 13, 1976, p. 69-86. | Numdam | MR 525458 | Zbl 0405.68063

6. S. Ginsburg, The Mathematical Theory of Context-free Languages, Mc Graw Hill, 1966. | MR 211815 | Zbl 0184.28401

7. S. Ginsburg et E.H. Spanier, Finite-Turn Pushdown Automata, S.I.A.M. J. Control, vol. 4, 1966, p. 429-453. | MR 204294 | Zbl 0147.25302

8. S. A. Greibach, The Unsolvability of the Recognition of Linear Context-Free Languages, J. Assoc. Comp. Mach., vol. 13, 1966, p. 582-588. | MR 205770 | Zbl 0148.00901

9. S. A. Greibach, One-Counter Languages and the IRS Condition, J. Comput System Sc., vol. 10, 1975, p. 237-247. | MR 395352 | Zbl 0307.68062

10. S. A. Greibach et E. Friedmann, Superdeterministics Pda's : a Subcase with a Decidable Equivalence Problem (à paraître). | Zbl 0462.68030

11. M. Latteux, Cônes Rationnels Commutativement Clos, R.A.I.R.O., Informatique Théorique, vol. 11, 1977, p. 29-51. | Numdam | MR 478782 | Zbl 0354.68103

12. R. E. Stearns, A Regularity Test for Pushdown Machines, Information and Control, vol. 11, 1967, p. 323-340. | Zbl 0155.01901

13. L. G. Valiant, The Equivalence Problem for Deterministic Finite-Turn Pushdow Automata, Information and Control, vol. 25, 1974, p. 123-133. | MR 391591 | Zbl 0285.68025

14. L. G. Valiant, Decision Procedures for Families of Deterministic Pushdown Automata, Ph. D. Thesis, University of Warwick, 1973.