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 mn2(log2n+m+42) 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.

Primitivity and Synchronizing Automata: A Functional Analytic Approach

Vladimir Protasov
2019

Abstract

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 mn2(log2n+m+42) 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
978-3-030-30806-3
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11697/159810
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact