Global One-Counter Tree Automata.

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

Abstract

We introduce global one-counter tree automata (GOCTA) which deviate from usual counter tree automata by working on only one counter which is passed through the tree in lexicographical order, rather than duplicating the counter at every branching position. We compare the capabilities of GOCTA to those of counter tree automata and obtain that their classes of recognizable tree languages are incomparable. Moreover, we show that the emptiness problem of GOCTA is undecidable while, in stark contrast, their membership problem is in P.

Details

OriginalspracheEnglisch
TitelImplementation and Application of Automata
Redakteure/-innenSzilárd Zsolt Fazekas
Herausgeber (Verlag)Springer
Seiten166-179
Seitenumfang14
ISBN (elektronisch)978-3-031-71112-1
ISBN (Print)978-3-031-71111-4
PublikationsstatusVeröffentlicht - 2024
Peer-Review-StatusJa

Publikationsreihe

ReiheLecture Notes in Computer Science, Volume 15015
ISSN0302-9743

Konferenz

Titel28th International Conference on Implementation and Application of Automata
KurztitelCIAA 2024
Veranstaltungsnummer28
Dauer3 - 6 September 2024
Webseite
BekanntheitsgradInternationale Veranstaltung
OrtAtorion
StadtAkita
LandJapan

Externe IDs

Scopus 85204379955

Schlagworte

Schlagwörter

  • global counter, one-counter automata, tree automata