s'authentifier
version française rss feed

hal-00749289, version 1

On One-Rule Grid Semi-Thue Systems

Michel Latteux () a1, Yves Roos (, http://www.lifl.fr/~yroos) a12

Fundamenta Informaticae 116, 1-4 (2012) 189-204

Résumé : The family of one-rule grid semi-Thue systems, introduced by Alfons Geser, is the family of one-rule semi-Thue systems such that there exists a letter c that occurs as often in the left-hand side as the right-hand side of the rewriting rule. We prove that for any one-rule grid semi-Thue system S, the set S(w) of all words obtainable from w using repeatedly the rewriting rule of S is a constructible context-free language. We also prove the regularity of the set Loop(S) of all words that start a loop in a one-rule grid semi-Thue systems S.

  • a –  Université des Sciences et Technologies de Lille - Lille I
  • 1 :  Laboratoire d'Informatique Fondamentale de Lille (LIFL)
  • CNRS : UMR8022 – Université Lille I - Sciences et technologies – Université Lille III - Sciences humaines et sociales – INRIA
  • 2 :  MOSTRARE (INRIA Lille - Nord Europe)
  • INRIA – CNRS : UMR8022 – Université Lille I - Sciences et technologies – Université Lille III - Sciences humaines et sociales
  • Domaine : Informatique/Théorie et langage formel
 
  • hal-00749289, version 1
  • oai:hal.inria.fr:hal-00749289
  • Contributeur : 
  • Soumis le : Mercredi 7 Novembre 2012, 11:12:31
  • Dernière modification le : Mercredi 7 Novembre 2012, 13:38:57
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...