Existe-t-il un livre / papier d'enquête décrivant les hiérarchies des classes de langues, les propriétés de fermeture, etc.

12

Je fais actuellement des recherches sur le langage formel impliquant des classes de langues au-dessus de Regular mais en dessous de Context Free. Je regarde des choses comme les machines à compteurs multiples inversées, les compteurs à pile unique, les LFC déterministes, etc.

Je me demande si quelqu'un connaît un bon livre ou un document d'enquête qui décrit les propriétés de ces langues. La plupart de ce que je regarde est trop obscur ou trop nouveau pour être dans mon livre Hopcroft-Ullman, même l'édition 1979.

Je recherche principalement les classes de langues qui sont contenues les unes dans les autres, les propriétés de fermeture de ces langues et la décidabilité des problèmes de base (problèmes F) sur ces langues.

Un exemple de choses que je rechercherais dans cette référence:

  • Est-ce que toutes les langues acceptées par les machines multi-compteurs à limite d'inversion sont également acceptées par les machines à compteur unique sans limite d'inversion?
  • Les langages MultiCounter bornés à l'inversion déterministe sont-ils fermés sous concaténation gauche et droite?
  • L'universalité est-elle décidable pour les machines à guichet unique.

Ce ne sont que des exemples de questions, j'en ai beaucoup d'autres qui reviennent dans mon travail quotidien.

Comme point de départ, j'ai essayé de retrouver les articles qui citent les machines à compteurs inversés et leurs problèmes de décision d'Oscar Ibarra, mais je n'ai pas trouvé grand-chose.

reference-request co.combinatorics fl.formal-languages automata-theory research-practice jmite
la source
3
Crossposted sur CS.SE .
Juho
2
Pour une analyse détaillée des machines à compteurs multiples à un état, voir Hiérarchies et caractérisations des machines à compteurs multiples sans état
Marzio De Biasi
2
... et je pense que beaucoup de documents / références peuvent être trouvés dans les articles
Marzio De Biasi
2
Avez-vous demandé à Oscar Ibarra?
Abuzer Yakaryilmaz
2
@jmite Il n'y a pas de mal à essayer :-) En tant qu'étudiant moi-même, j'ai toujours reçu une réponse d'un chercheur lorsque je leur ai envoyé un e-mail. D'après mon expérience, les gens ne sont heureux d'aider qu'une personne intéressée par leur recherche.
Juho

Réponses:

5

Pas de sujets standard, non. Et désolé, je n'ai pas de vue d'ensemble.

Cependant, je voudrais jeter un œil à la thèse de doctorat de Klaus Reinhardt pour au moins une photo des différentes familles qui vivent dans ce domaine. Voir page 64 pour un schéma du zoo. Motivé par des réseaux de Petri avec des arcs inhibiteurs, Reinhardt étudie les multicompteurs prioritaires avec des restrictions sur le moment de faire des tests zéro. Non trivial.

Soit dit en passant, votre dernier exemple de question a été discuté dans ce forum par l'utilisateur Sam Jones. Une autre référence Ibarra.

Hendrik Jan
la source