On a class of languages with holonomic generating functions

Giuseppa Castiglione, Paolo Massazza

Risultato della ricerca: Article

5 Citazioni (Scopus)

Abstract

We define a class of languages (RCM) obtained by considering Regular languages, linear Constraints on the number of occurrences of symbols and Morphisms. The class RCM presents some interesting closure properties, and contains languages with holonomic generating functions. As a matter of fact, RCM is related to one-way 1-reversal bounded k-counter machines and also to Parikh automata on letters. Indeed, RCM is contained in L-NFCM but not in L-DFCM, and strictly includes L-CPA. We conjecture that L-DFCM subset of RCM
Lingua originaleEnglish
pagine (da-a)74-84
Numero di pagine11
RivistaTheoretical Computer Science
Volume658
Stato di pubblicazionePublished - 2017

Fingerprint

Formal languages
Generating Function
Closure Properties
Regular Languages
Linear Constraints
Morphisms
Reversal
Automata
Strictly
Subset
Class
Language

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cita questo

On a class of languages with holonomic generating functions. / Castiglione, Giuseppa; Massazza, Paolo.

In: Theoretical Computer Science, Vol. 658, 2017, pag. 74-84.

Risultato della ricerca: Article

@article{86cacf8bb0a641858cf644456a03bca7,
title = "On a class of languages with holonomic generating functions",
abstract = "We define a class of languages (RCM) obtained by considering Regular languages, linear Constraints on the number of occurrences of symbols and Morphisms. The class RCM presents some interesting closure properties, and contains languages with holonomic generating functions. As a matter of fact, RCM is related to one-way 1-reversal bounded k-counter machines and also to Parikh automata on letters. Indeed, RCM is contained in L-NFCM but not in L-DFCM, and strictly includes L-CPA. We conjecture that L-DFCM subset of RCM",
keywords = "Context free languages; Holonomic functions; k-counter machines; Parikh automata; Parikh vectors; Theoretical Computer Science; Computer Science (all)",
author = "Giuseppa Castiglione and Paolo Massazza",
year = "2017",
language = "English",
volume = "658",
pages = "74--84",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

TY - JOUR

T1 - On a class of languages with holonomic generating functions

AU - Castiglione, Giuseppa

AU - Massazza, Paolo

PY - 2017

Y1 - 2017

N2 - We define a class of languages (RCM) obtained by considering Regular languages, linear Constraints on the number of occurrences of symbols and Morphisms. The class RCM presents some interesting closure properties, and contains languages with holonomic generating functions. As a matter of fact, RCM is related to one-way 1-reversal bounded k-counter machines and also to Parikh automata on letters. Indeed, RCM is contained in L-NFCM but not in L-DFCM, and strictly includes L-CPA. We conjecture that L-DFCM subset of RCM

AB - We define a class of languages (RCM) obtained by considering Regular languages, linear Constraints on the number of occurrences of symbols and Morphisms. The class RCM presents some interesting closure properties, and contains languages with holonomic generating functions. As a matter of fact, RCM is related to one-way 1-reversal bounded k-counter machines and also to Parikh automata on letters. Indeed, RCM is contained in L-NFCM but not in L-DFCM, and strictly includes L-CPA. We conjecture that L-DFCM subset of RCM

KW - Context free languages; Holonomic functions; k-counter machines; Parikh automata; Parikh vectors; Theoretical Computer Science; Computer Science (all)

UR - http://hdl.handle.net/10447/254435

UR - http://www.journals.elsevier.com/theoretical-computer-science/

M3 - Article

VL - 658

SP - 74

EP - 84

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -