Regular and context-free nominal traces

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

    Pierpaolo Degano, Dipartimento di Informatica, Università di Pisa, Pisa, Italy, ItalyGian-Luigi Ferrari, Dipartimento di Informatica, Università di Pisa, Pisa, Italy, ItalyGianluca Mezzetti, Dipartimento di Informatica, Università di Pisa, Pisa, Italy
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
Volume54
Issue number4
Pages (from-to)399-433
Number of pages35
ISSN0001-5903
DOIs
StatePublished - 2017

See relations at Aarhus University Citationformats

ID: 108487081