Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BYCC-BY - Uznanie autorstwa
 

Parikh One-Counter Automata

Uproszczony widok
dc.abstract.enParikh One-Counter Automata Michaël Cadilhac # DePaul University, Chicago, IL, USA Arka Ghosh # University of Warsaw, Poland Guillermo A. Pérez # University of Antwerp – Flanders Make, Belgium Ritam Raha # University of Antwerp – Flanders Make, Belgium LaBRI, University of Bordeaux, France Abstract Counting abilities in finite automata are traditionally provided by two orthogonal extensions: adding a single counter that can be tested for zeroness at any point, or adding Z-valued counters that are tested for equality only at the end of runs. In this paper, finite automata extended with both types of counters are introduced. They are called Parikh One-Counter Automata (POCA): the “Parikh” part referring to the evaluation of counters at the end of runs, and the “One-Counter” part to the single counter that can be tested during runs. Their expressiveness, in the deterministic and nondeterministic variants, is investigated; it is shown in particular that there are deterministic POCA languages that cannot be expressed without nondeterminism in the original models. The natural decision problems are also studied; strikingly, most of them are no harder than in the original models. A parametric version of nonemptiness is also considered.
dc.affiliationUniwersytet Warszawski
dc.conference.countryFrancja
dc.conference.datefinish2023-09-01
dc.conference.datestart2023-08-28
dc.conference.placeBordoux
dc.conference.seriesInternational Symposium on Mathematical Foundations of Computer Science
dc.conference.seriesInternational Symposium on Mathematical Foundations of Computer Science
dc.conference.seriesshortcutMFCS
dc.conference.shortcut(MFCS 2023)
dc.contributor.authorRaha, Ritam
dc.contributor.authorPérez, Guillermo A.
dc.contributor.authorGhosh, Arka
dc.contributor.authorCadilhac, Michaël
dc.date.accessioned2024-01-25T16:21:03Z
dc.date.available2024-01-25T16:21:03Z
dc.date.copyright2023-08-21
dc.date.issued2023
dc.description.accesstimeAT_PUBLICATION
dc.description.financePublikacja bezkosztowa
dc.description.versionFINAL_PUBLISHED
dc.identifier.doi10.4230/LIPICS.MFCS.2023.30
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/115524
dc.identifier.weblinkhttps://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.30
dc.languageeng
dc.relation.pages1-15
dc.rightsCC-BY
dc.sciencecloudnosend
dc.titleParikh One-Counter Automata
dc.typeJournalArticle
dspace.entity.typePublication