Regular and context-free nominal traces

Research output: Research - peer-reviewJournal article


  • Pierpaolo Degano
    Pierpaolo DeganoDipartimento di Informatica, Università di Pisa, Pisa, ItalyItaly
  • Gian-Luigi Ferrari
    Gian-Luigi FerrariDipartimento di Informatica, Università di Pisa, Pisa, ItalyItaly
  • Gianluca Mezzetti
Two kinds of automata are presented, for recognising new classes of regular and context-free nominal languages. We compare their expressive power with analogous proposals in the literature, showing that they express novel classes of languages. Although many properties of classical languages hold no longer in the nominal case, we design a slight restriction of our models that preserve some interesting ones. In particular, we prove the emptiness problem decidable and we construct the intersection between (restricted) regular and context-free automata. By examples and walking through their properties we argue the relevance of our models in the context of the verification of resource usage patterns.
Original languageEnglish
JournalActa Informatica
Issue number4
Pages (from-to)399-433
Number of pages35
StatePublished - 2017

See relations at Aarhus University Citationformats

ID: 108487081