Data di Pubblicazione:
2017
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.
Tipologia CRIS:
Relazione (in Volume)
Keywords:
Theoretical Computer Science; Computer Science (all)
Elenco autori:
Massazza, Paolo
Link alla scheda completa:
Titolo del libro:
Implementation and Application of Automata
Pubblicato in: