Indécidabilité de la condition IRS

Jean-Michel Autebert; Joffroy Beauquier; Luc Boasson; Michel Latteux

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1982)

  • Volume: 16, Issue: 2, page 129-138
  • ISSN: 0988-3754

How to cite

top

Autebert, Jean-Michel, et al. "Indécidabilité de la condition IRS." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 16.2 (1982): 129-138. <http://eudml.org/doc/92156>.

@article{Autebert1982,
author = {Autebert, Jean-Michel, Beauquier, Joffroy, Boasson, Luc, Latteux, Michel},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {context-free language; linear language; deterministic language; rational language; IRS condition; decidability; Post's correspondence problem},
language = {fre},
number = {2},
pages = {129-138},
publisher = {EDP-Sciences},
title = {Indécidabilité de la condition IRS},
url = {http://eudml.org/doc/92156},
volume = {16},
year = {1982},
}

TY - JOUR
AU - Autebert, Jean-Michel
AU - Beauquier, Joffroy
AU - Boasson, Luc
AU - Latteux, Michel
TI - Indécidabilité de la condition IRS
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1982
PB - EDP-Sciences
VL - 16
IS - 2
SP - 129
EP - 138
LA - fre
KW - context-free language; linear language; deterministic language; rational language; IRS condition; decidability; Post's correspondence problem
UR - http://eudml.org/doc/92156
ER -

References

top
  1. 1. J. M. AUTEBERT, G. COUSINEAU et M. NIVAT, Les Langages Algébriques, Hermann, Paris (à paraître). 
  2. 2. L. BOASSON, Un LangageAlgébrique Particulier, R.A.I.R.O., Informatique théorique, vol. 13, 1979, p. 203-215. Zbl0424.68042MR554682
  3. 4. E. FRIEDMANN, The Inclusion Problem for Simple Languages, Theoretical Computer Science, vol. 1, 1976, p. 297-316. Zbl0349.68032MR405936
  4. 5. C. FROUGNY, Langages très Simples Générateurs, R.A.I.R.O., Informatique Théorique, vol. 13, 1976, p. 69-86. Zbl0405.68063MR525458
  5. 6. S. GINSBURG, The Mathematical Theory of Context-free Languages, Mc Graw Hill, 1966. Zbl0184.28401MR211815
  6. 7. S. GINSBURG et E.H. SPANIER, Finite-Turn Pushdown Automata, S.I.A.M. J. Control, vol. 4, 1966, p. 429-453. Zbl0147.25302MR204294
  7. 8. S. A. GREIBACH, The Unsolvability of the Recognition of Linear Context-Free Languages, J. Assoc. Comp. Mach., vol. 13, 1966, p. 582-588. Zbl0148.00901MR205770
  8. 9. S. A. GREIBACH, One-Counter Languages and the IRS Condition, J. Comput System Sc., vol. 10, 1975, p. 237-247. Zbl0307.68062MR395352
  9. 10. S. A. GREIBACH et E. FRIEDMANN, Superdeterministics Pda's : a Subcase with a Decidable Equivalence Problem (à paraître). Zbl0462.68030
  10. 11. M. LATTEUX, Cônes Rationnels Commutativement Clos, R.A.I.R.O., Informatique Théorique, vol. 11, 1977, p. 29-51. Zbl0354.68103MR478782
  11. 12. R. E. STEARNS, A Regularity Test for Pushdown Machines, Information and Control, vol. 11, 1967, p. 323-340. Zbl0155.01901
  12. 13. L. G. VALIANT, The Equivalence Problem for Deterministic Finite-Turn Pushdow Automata, Information and Control, vol. 25, 1974, p. 123-133. Zbl0285.68025MR391591
  13. 14. L. G. VALIANT, Decision Procedures for Families of Deterministic Pushdown Automata, Ph. D. Thesis, University of Warwick, 1973. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.