1 Search Results for "Pattathurajan, Mohnish"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.50
Parikh Images of Register Automata

Authors: Sławomir Lasota and Mohnish Pattathurajan

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

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.
Cite as

Sławomir Lasota and Mohnish Pattathurajan. Parikh Images of Register Automata. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.50},
  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}
}
  • Refine by Author
  • 1 Lasota, Sławomir
  • 1 Pattathurajan, Mohnish

  • Refine by Classification
  • 1 Theory of computation → Automata over infinite objects

  • Refine by Keyword
  • 1 Parikh images
  • 1 Sets with atoms
  • 1 hierarchical register automata
  • 1 rational sets
  • 1 register automata

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact