2026-07-23T03:47:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15561 2024-03-06T10:55:36Z ddc:004 open_access

Parikh Images of Register Automata Lasota, Sławomir Pattathurajan, Mohnish Sets with atoms register automata Parikh images rational sets hierarchical register automata As it has been recently shown, Parikh images of languages of nondeterministic one-register automata are rational (but not semilinear in general), but it is still open if the property extends to all register automata. We identify a subclass of nondeterministic register automata, called hierarchical register automata (HRA), with the following two properties: every rational language is recognised by a HRA; and Parikh image of the language of every HRA is rational. In consequence, these two properties make HRA an automata-theoretic characterisation of languages of nondeterministic register automata with rational Parikh images. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sławomir Lasota and Mohnish Pattathurajan 2021 Is Part Of LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2021.50 urn:nbn:de:0030-drops-155613 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.50 eng https://creativecommons.org/licenses/by/4.0/legalcode