Rational Graphs Trace Context-Sensitive Languages

1. Autebert, J.-M. and Boasson, L.Transductions rationelles. Masson, 1988.

   Google Scholar 

2. Berstel, J.Transductions and contextfree languages. Teubner, 1979.

   Google Scholar 

3. Moller, F. Burkart, O., Caucal, D. and Steffen B.Handbook of Process Algebra, chapter Verification on infinite structures, pages 545–623. Elsevier, 2001.

   Google Scholar 

4. Caucal, D. On transition graphs having a decidable monadic theory. In Icalp 96, volume 1099 of LNCS, pages 194–205, 1996.

   Google Scholar 

5. Courcelle, B.Handbook of Theoretical Computer Science, chapter Graph rewriting: an algebraic and logic approach. Elsevier, 1990.

   Google Scholar 

6. Ginsburg, S. and Rose, G. F. Preservation of languages by transducers. Information and control, 9:153–176, 1966.

   Article  MATH  MathSciNet  Google Scholar 

7. Knapik, T. and Payet, E. Synchronization product of linear bounded machines. In FCT, volume 1684 of LNCS, pages 362–373, 1999.

   Google Scholar 

8. Mateescu, A., Salomaa, A.Handbook of Formal Languages, volume 1, chapter Aspects of classical language theory, pages 175–252. Springer-Verlag, 1997.

   Google Scholar 

9. Morvan, C. On rational graphs. In Fossacs 00, volume 1784 of LNCS, pages 252–266, 2000.

   Google Scholar 

10. Muller, D. and Schupp, P. The theory of ends, pushdown automata, and secondorder logic. Theoretical Computer Science, 37:51–75, 1985.

    Article  MATH  MathSciNet  Google Scholar 

11. Penttonen, M. One-sided and two-sided context in formal grammars. Information and Control, 25:371–392, 1974.

    Article  MATH  MathSciNet  Google Scholar 

Download references