Global One-Counter Tree Automata.

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-review

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

Original languageEnglish
Title of host publicationImplementation and Application of Automata
EditorsSzilárd Zsolt Fazekas
PublisherSpringer
Pages166-179
Number of pages14
ISBN (electronic)978-3-031-71112-1
ISBN (print)978-3-031-71111-4
Publication statusPublished - 2024
Peer-reviewedYes

Publication series

SeriesLecture Notes in Computer Science, Volume 15015
ISSN0302-9743

Conference

Title28th International Conference on Implementation and Application of Automata
Abbreviated titleCIAA 2024
Conference number28
Duration3 - 6 September 2024
Website
Degree of recognitionInternational event
LocationAtorion
CityAkita
CountryJapan

External IDs

Scopus 85204379955

Keywords

Keywords

  • global counter, one-counter automata, tree automata