ISSN: 2310-757X
Please use this identifier to cite or link to this item:
http://elar.urfu.ru/handle/10995/75714| Title: | Synchronizing monotonic automata |
| Authors: | Ananichev, D. S. Volkov, M. V. |
| Issue Date: | 2004 |
| Citation: | Ananichev D. S. Synchronizing monotonic automata / D. S. Ananichev, M. V. Volkov // Theoretical Computer Science. — 2004. — Vol. 327. — Iss. 3. — P. 225-239. |
| Abstract: | We show that if the state set Q of a synchronizing automaton A = (Q, ∑, δ) admits a linear order such that for each letter a ∈ ∑ the transformation δ(_, a) of β preserves this order, then A possesses a reset word of length |Q| - 1. We also consider two natural generalizations of the notion of a reset word and provide for them results of a similar flavour. © 2004 Elsevier B.V. All rights reserved. |
| Keywords: | INTERVAL RANK OF A WORD MONOTONIC AUTOMATA ORDER PRESERVING TRANSFORMATION RANK OF A WORD SYNCHRONIZING AUTOMATA AUTOMATION MATHEMATICAL TRANSFORMATIONS ROBOTICS SET THEORY SYNCHRONIZATION THEOREM PROVING INTERVAL RANK OF A WORD MONOTONIC AUTOMATA ORDER PRESERVING TRANSFORMATION RANK OF A WORD SYNCHRONIZING AUTOMATA AUTOMATA THEORY |
| URI: | http://elar.urfu.ru/handle/10995/75714 |
| Access: | info:eu-repo/semantics/openAccess |
| Conference name: | Developments in Language Theory |
| Conference date: | 7 July 2003 through 11 July 2003 |
| SCOPUS ID: | 6344237329 |
| WOS ID: | 000224865300002 |
| PURE ID: | 7882917 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2004.03.068 |
| Sponsorship: | Several useful comments of the anonymous referees of the proceedings version [1] of this paper are gratefully acknowledged. The authors acknowledge support from the Education Ministry of Russian Federation, Grants E02-1.0-143 and 04.01.059, the Russian Foundation for Basic Research, Grant 01-01-00258, the President Program of Leading Scientific Schools, Grant 2227.2003.1, and the INTAS (through Network Project 99-1224 “Combinatorial and Geometric Theory of Groups and Semigroups and its Applications to Computer Science”). |
| Appears in Collections: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 1-s2.0-S0304397504004797.pdf | 243,18 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.