On the Smallest Synchronizing Terms of Finite Tree Automata

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F23%3A00368009" target="_blank" >RIV/68407700:21240/23:00368009 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1007/978-3-031-40247-0_5" target="_blank" >https://doi.org/10.1007/978-3-031-40247-0_5</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-40247-0_5" target="_blank" >10.1007/978-3-031-40247-0_5</a>

Result language

angličtina

Original language name

On the Smallest Synchronizing Terms of Finite Tree Automata

Original language description

This paper deals with properties of synchronizing terms for finite tree automata, which is a generalization of the synchronization principle of deterministic finite string automata (DFA) and such terms correspond to a connected subgraph, where a state in the root is always the same regardless of states of subtrees attached to it. We ask, what is the maximum height of the smallest synchronizing term of a deterministic bottom-up tree automaton (DFTA) with n states, which naturally leads to two types of synchronizing terms, called weak and strong, that depend on whether a variable, i.e., a placeholder for a subtree, must be present in at least one leaf or all of them. We prove that the maximum height in the case of weak synchronization has a theoretical upper bound sl(????)+????-1, where sl(????) is the maximum length of the shortest synchronizing string of an n-state DFAs. For strong synchronization, we prove exponential bounds. We provide a theoretical upper bound of 2^????-????-1 for the height and two constructions of automata approaching it. One achieves the height of Θ(2^(????-root ????)) with an alphabet of linear size, and the other achieves 2^(????-1)-1 with an alphabet of quadratic size.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Research Center for Informatics</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2023

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Implementation and Application of Automata

ISBN

978-3-031-40247-0

ISSN

0302-9743

e-ISSN

1611-3349

Number of pages

12

Pages from-to

79-90

Publisher name

Springer, Cham

Place of publication

—

Event location

Famagusta

Event date

Sep 19, 2023

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

001360247600005