Wyniki wyszukiwania - BazTech

1

A Linear Bound on the k-rendezvous Time for Primitive Sets of NZ Matrices

Catalano Costanza, Azfar Umer, Charlier Ludovic, Jungers Raphaël M.

Fundamenta Informaticae

|

2021

|

Vol. 180, nr 4

289--314

EN

A set of nonnegative matrices is called primitive if there exists a product of these matrices that is entrywise positive. Motivated by recent results relating synchronizing automata and primitive sets, we study the length of the shortest product of a primitive set having a column or a row with k positive entries, called its k-rendezvous time (k-RT), in the case of sets of matrices having no zero rows and no zero columns. We prove that the k-RT is at most linear w.r.t. the matrix size n for small k, while the problem is still open for synchronizing automata. We provide two upper bounds on the k-RT: the second is an improvement of the first one, although the latter can be written in closed form. We then report numerical results comparing our upper bounds on the k-RT with heuristic approximation methods.

2

Trim Strongly Connected Synchronizing Automata and Ideal Languages

Maslennikova M., Rodaro E.

Fundamenta Informaticae

|

2018

|

Vol. 162, nr 2/3

183--203

EN

We follow language theoretic approach to synchronizing automata and Černý’s conjecture initiated in a series of recent papers. We prove that for every ideal language there exists a strongly connected synchronizing automaton from some special class for which given language serves as the language of reset words. This class is formed by trim automata recognizing left quotients of principal left ideal languages. We show that the minimal automaton recognizing a left quotient of a principal left ideal can be viewed as a synchronizing automaton for which given finitely generated ideal serves as the language of reset words.

3

Subset Synchronization in Monotonic Automata

Ryzhikov A., Shemyakov A.

Fundamenta Informaticae

|

2018

|

Vol. 162, nr 2/3

205--221

EN

We study extremal and algorithmic questions of subset and careful synchronization in monotonic automata. We show that several synchronization problems that are hard in general automata can be solved in polynomial time in monotonic automata, even without knowing a linear order of the states preserved by the transitions. We provide asymptotically tight bounds on the maximum length of a shortest word synchronizing a subset of states in a monotonic automaton and a shortest word carefully synchronizing a partial monotonic automaton. We provide a complexity framework for dealing with problems for monotonic weakly acyclic automata over a three-letter alphabet, and use it to prove NP-completeness and inapproximability of problems such as FINITE AUTOMATA INTERSECTION and the problem of computing the rank of a subset of states in this class. We also show that checking whether a monotonic partial automaton over a four-letter alphabet is carefully synchronizing is NP-hard. Finally, we give a simple necessary and sufficient condition when a strongly connected digraph with a selected subset of vertices can be transformed into a deterministic automaton where the corresponding subset of states is synchronizing.

4

Principal Ideal Languages and Synchronizing Automata

Gusev V. V., Maslennikova M. I., Pribavkina E. V.

Fundamenta Informaticae

|

2014

|

Vol. 132, nr 1

95--108

EN

We study ideal languages generated by a single word. We provide an algorithm to construct a strongly connected synchronizing automaton for which such a language serves as the language of synchronizing words. Also we present a compact formula to calculate the syntactic complexity of this language.

5

The Computational Complexity of Universality Problems for Prefixes, Suffixes, Factors, and Subwords of Regular Languages

Rampersad N., Shallit J., Xu Z.

Fundamenta Informaticae

|

2012

|

Vol. 116, nr 1-4

223-236

EN

In this paper we consider the computational complexity of the following problems: given a DFA or NFA representing a regular language L over a finite alphabet Σ, is the set of all prefixes (resp., suffixes, factors, subwords) of all words of L equal to Σ*? In the case of testing universality for factors of languages, there is a connection to two classic problems: the synchronizing words problem of Černy, and Restivo's conjecture on the minimal uncompletable word.