We prove that the class of the languages recognized by one-way deterministic 1-reversal bounded 1-counter machines is contained in RCM, a class of languages that has been recently introduced and that admits interesting properties. This is the first step to prove the conjecture LDFCM â RCM, which says that for any fixed integer k all the languages recognized by one-way deterministic 1-reversal bounded k-counter machines are in RCM. We recall that this conjecture implies that the generating function of a language in LDFCM is holonomic.
|Titolo:||On the conjecture LDFCM ⊊ RCM|
|Data di pubblicazione:||2017|
|Appare nelle tipologie:||Relazione (in Volume)|