Primitivity and Synchronizing Automata: A Functional Analytic Approach
| العنوان: | Primitivity and Synchronizing Automata: A Functional Analytic Approach |
|---|---|
| المؤلفون: | Vladimir Yu. Protasov |
| المصدر: | Lecture Notes in Computer Science ISBN: 9783030308056 RP |
| بيانات النشر: | Springer International Publishing, 2019. |
| سنة النشر: | 2019 |
| مصطلحات موضوعية: | Discrete mathematics, Nonnegative matrix, Contraction, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, Affine operator, Functional equation, Primitive semigroups, Synchrinizing automata, Synchronizing automaton, Automaton, Tuple, Contraction (operator theory), Computer Science::Databases, Computer Science::Formal Languages and Automata Theory, Mathematics |
| الوصف: | We give a survey of a function-analytic approach in the study of primitivity of matrix families and of synchronizing automata. Then we define the m-synchronising automata and prove that the existence of a reset m-tuple of a deterministic automata with n states can be decided in less than \(m n^2 \bigl (\log _2 n + \frac{m+4}{2}\bigr )\) operations. We study whether the functional-analytic approach can be extended to m-primitivity and to m-synchronising automata. Several open problems and conjectures concerning the length of m-reset tuples, m-primitive products and finding those objects algorithmically are formulated. |
| ردمك: | 978-3-030-30805-6 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::684ee483516fd2f133296847c79cf00f https://doi.org/10.1007/978-3-030-30806-3_2 |
| حقوق: | CLOSED |
| رقم الأكسشن: | edsair.doi.dedup.....684ee483516fd2f133296847c79cf00f |
| قاعدة البيانات: | OpenAIRE |
| ردمك: | 9783030308056 |
|---|