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.
On the conjecture LDFCM ⊊ RCM
MASSAZZA, PAOLO
2017-01-01
Abstract
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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
