Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
On the smallest synchronizing terms of finite tree automata
University of Warwick, Coventry, United Kingdom.
Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Thákurova 9, Prague, Czech Republic.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Thákurova 9, Prague, Czech Republic.ORCID-id: 0000-0003-3783-8870
2025 (Engelska)Ingår i: International Journal of Foundations of Computer Science, ISSN 0129-0541Artikel i tidskrift (Refereegranskat) Epub ahead of print
Abstract [en]

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). 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. This 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(n)+n-1, where sl(n) 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 2n-n-1 for the height and two constructions of automata approaching it. One achieves the height of θ (2n-r√n) with an alphabet of linear size and maximum arity r, and the other achieves 2n-1-1 with an alphabet of quadratic size.

Ort, förlag, år, upplaga, sidor
World Scientific, 2025.
Nyckelord [en]
automata theory, Cerný conjecture, synchronizing string, synchronizing term, Tree automata
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:umu:diva-245759DOI: 10.1142/S0129054125410096ISI: 001567924400001Scopus ID: 2-s2.0-105015469565OAI: oai:DiVA.org:umu-245759DiVA, id: diva2:2007938
Forskningsfinansiär
Vetenskapsrådet, 2020-03852Wallenberg AI, Autonomous Systems and Software Program (WASP)Tillgänglig från: 2025-10-21 Skapad: 2025-10-21 Senast uppdaterad: 2025-10-21

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Plachý, Štěpán

Sök vidare i DiVA

Av författaren/redaktören
Plachý, Štěpán
Av organisationen
Institutionen för datavetenskap
I samma tidskrift
International Journal of Foundations of Computer Science
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 27 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf