On the Smallest Synchronizing Terms of Finite Tree Automata

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

On the Smallest Synchronizing Terms of Finite Tree Automata

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On the Smallest Synchronizing Terms of Finite Tree Automata

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Výzkumné centrum informatiky</a><br>

Návaznosti

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

Rok uplatnění

2023

Kód důvěrnosti údajů

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

Název statě ve sborníku

Implementation and Application of Automata

ISBN

978-3-031-40247-0

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

12

Strana od-do

79-90

Název nakladatele

Springer, Cham

Místo vydání

—

Místo konání akce

Famagusta

Datum konání akce

19. 9. 2023

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001360247600005