The Library
On the smallest synchronizing terms of finite tree automata
Tools
Blazej, Vaclav, Janoušek, Jan and Plachý, Štěpán (2023) On the smallest synchronizing terms of finite tree automata. In: 27th International Conference, CIAA 2023, Famagusta, North Cyprus, 19–22 Sep 2023. Published in: Implementation and Application of Automata. CIAA 2023, 14151 pp. 79-90. doi:10.1007/978-3-031-40247-0_5 ISSN 0302-9743.
PDF
WRAP-On-the-smallest-synchronizing-terms-finite-23.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only until 10 August 2024. Contact author directly, specifying your specific needs. - Requires a PDF viewer. Download (552Kb) |
Official URL: https://doi.org/10.1007/978-3-031-40247-0_5
Abstract
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(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−n√) with an alphabet of linear size, and the other achieves 2n−1−1 with an alphabet of quadratic size.
Item Type: | Conference Item (Paper) | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||
Library of Congress Subject Headings (LCSH): | Machine theory, Machine theory -- Mathematical models, Trees (Graph theory) | ||||||||||||
Series Name: | Lecture Notes in Computer Science | ||||||||||||
Journal or Publication Title: | Implementation and Application of Automata. CIAA 2023 | ||||||||||||
Publisher: | Springer | ||||||||||||
ISSN: | 0302-9743 | ||||||||||||
Book Title: | Implementation and Application of Automata | ||||||||||||
Official Date: | 10 August 2023 | ||||||||||||
Dates: |
|
||||||||||||
Volume: | 14151 | ||||||||||||
Page Range: | pp. 79-90 | ||||||||||||
DOI: | 10.1007/978-3-031-40247-0_5 | ||||||||||||
Status: | Not Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||
Date of first compliant deposit: | 2 October 2023 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Conference Paper Type: | Paper | ||||||||||||
Title of Event: | 27th International Conference, CIAA 2023 | ||||||||||||
Type of Event: | Conference | ||||||||||||
Location of Event: | Famagusta, North Cyprus | ||||||||||||
Date(s) of Event: | 19–22 Sep 2023 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |