Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2021.50
URN: urn:nbn:de:0030-drops-155613
URL: https://drops.dagstuhl.de/opus/volltexte/2021/15561/
Lasota, Sławomir ; Pattathurajan, Mohnish
Parikh Images of Register Automata
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{lasota_et_al:LIPIcs.FSTTCS.2021.50,
author = {Lasota, S{\l}awomir and Pattathurajan, Mohnish},
title = {{Parikh Images of Register Automata}},
booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
pages = {50:1--50:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-215-0},
ISSN = {1868-8969},
year = {2021},
volume = {213},
editor = {Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15561},
URN = {urn:nbn:de:0030-drops-155613},
doi = {10.4230/LIPIcs.FSTTCS.2021.50},
annote = {Keywords: Sets with atoms, register automata, Parikh images, rational sets, hierarchical register automata}
}
| Keywords: | Sets with atoms, register automata, Parikh images, rational sets, hierarchical register automata | |
| Seminar: | 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 29.11.2021 |
