BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

A. N. Trahtman

A. N. Trahtman contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Discrete MathematicsFormal Languages and Automata Theory

Trust snapshot

Quick read

Trust 21 - Emerging
8works
0followers
2topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2022arXiv

A Partially Synchronizing Coloring

Given a finite directed graph, a coloring of its edges turns the graph into a finite-state automaton. A k-synchronizing word of a deterministic automaton is a word in the alphabet of colors at its edges that maps the state set of the automaton at least on k-element subset. A coloring of edges of a directed strongly connected finite graph of a uniform outdegree (constant outdegree of any vertex) is k-synchronizing if the coloring turns the graph into a deterministic finite automaton possessing a k-synchronizing word. For k=1 one has the well known road coloring problem. The recent positive solution of the road coloring problem implies an elegant generalization considered first by Beal and Perrin: a directed finite strongly connected graph of uniform outdegree is k-synchronizing iff the greatest common divisor of lengths of all its cycles is k. Some consequences for coloring of an arbitrary finite digraph are presented. We describe a subquadratic algorithm of the road coloring for the k-synchronization implemented in the package TESTAS. A new linear visualization program demonstrates the obtained coloring. Some consequences for coloring of an arbitrary finite digraph and of such a graph of uniform outdegree are presented.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A polynomial time algorithm for local testability and its level

A locally testable semigroup S is a semigroup with the property that for some nonnegative integer k, called the order or level of local testability, two words u and v in some set of generators for semigroup S are equal in the semigroup if (1) the prefix and suffix of the words of length k coincide, and (2) the set of intermediate substrings of length k of the words coincide. The local testability problem for semigroups is, given a finite semigroup, to decide, if the semigroup is locally testable or not. Recently, we introduced a polynomial time algorithm for the local testability problem and to find the level of local testability for semigroups based on our previous description of identities of $k$-testable semigroups and the structure of locally testable semigroups. The first part of the algorithm we introduce solves the local testability problem. The second part of the algorithm finds the order of local testability of a semigroup. The algorithm is of quadratic order where n is the order of the semigroup.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Černy conjecture

A word $w$ of letters on edges of underlying graph $Γ$ of deterministic finite automaton (DFA) is called synchronizing if $w$ sends all states of the automaton to a unique state. J. Černy discovered in 1964 a sequence of $n$-state complete DFA possessing a minimal synchronizing word of length $(n-1)^2$. The hypothesis, well known today as the Černy conjecture, claims that it is also precise upper bound on the length of such a word for a complete DFA. The hypothesis was formulated in 1966 by Starke. The problem has motivated great and constantly growing number of investigations and generalizations. To prove the conjecture, we use algebra w on a special class of row monomial matrices (one unit and rest zeros in every row), induced by words in the alphabet of labels on edges. These matrices generate a space with respect to the mentioned operation. The proof is based on connection between length of words $u$ and dimension of the space generated by solutions $L_x$ of matrix equation $M_uL_x=M_s$ for synchronizing word $s$, as well as on the relation between ranks of $M_u$ and $L_x$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Modifying the upper bound on the length of minimal synchronizing word

A word $w$ is called synchronizing (recurrent, reset, magic, directable) word of deterministic finite automaton (DFA) if $w$ sends all states of the automaton to a unique state. In 1964 Jan Černy found a sequence of n-state complete DFA possessing a minimal synchronizing word of length $(n-1)^2$. He conjectured that it is an upper bound on the length of such words for complete DFA. Nevertheless, the best upper bound $(n^3-n)/6$ was found almost 30 years ago. We reduce the upper bound on the length of the minimal synchronizing word to $n(7n^2+6n-16)/48$. An implemented algorithm for finding synchronizing word with restricted upper bound is described. The work presents the distribution of all synchronizing automata of small size according to the length of an almost minimal synchronizing word.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

An Algorithm for Road Coloring

A coloring of edges of a finite directed graph turns the graph into finite-state automaton. The synchronizing word of a deterministic automaton is a word in the alphabet of colors (considered as letters) of its edges that maps the automaton to a single state. A coloring of edges of a directed graph of uniform outdegree (constant outdegree of any vertex) is synchronizing if the coloring turns the graph into a deterministic finite automaton possessing a synchronizing word. The road coloring problem is the problem of synchronizing coloring of a directed finite strongly connected graph of uniform outdegree if the greatest common divisor of the lengths of all its cycles is one. The problem posed in 1970 had evoked a noticeable interest among the specialists in the theory of graphs, automata, codes, symbolic dynamics as well as among the wide mathematical community. A polynomial time algorithm of $O(n^3)$ complexity in the most worst case and quadratic in majority of studied cases for the road coloring of the considered graph is presented below. The work is based on recent positive solution of the road coloring problem. The algorithm was implemented in the package TESTAS

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Visualization of the Road Coloring Algorithm in the package TESTAS

A synchronizing word of a deterministic automaton is a word in the alphabet of colors of its edges that maps the automaton to a single state. A coloring of edges of a directed graph is synchronizing if the coloring turns the graph into a deterministic finite automaton possessing a synchronizing word. The road coloring problem is the problem of synchronizing coloring of a directed finite strongly connected graph with constant outdegree of all its vertices if the greatest common divisor of the lengths of all its cycles is one. A polynomial time algorithm of the road coloring has been based on recent positive solution of this old famous problem. One can use our new visualization program for demonstration of the algorithm as well as for visualization of the transition graph of any finite automaton. The visual image presents some structure properties of the transition graph. This help tool is linear in the size of the automaton.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

The road coloring problem

The synchronizing word of deterministic automaton is a word in the alphabet of colors (considered as letters) of its edges that maps the automaton to a single state. A coloring of edges of a directed graph is synchronizing if the coloring turns the graph into deterministic finite automaton possessing a synchronizing word. The road coloring problem is a problem of synchronizing coloring of directed finite strongly connected graph with constant outdegree of all its vertices if the greatest common divisor of lengths of all its cycles is one. The problem was posed by Adler, Goodwyn and Weiss over 30 years ago and evoked a noticeable interest among the specialists in theory of graphs, deterministic automata and symbolic dynamics. The problem is described even in "Wikipedia" - the popular Internet Encyclopedia. The positive solution of the road coloring problem is presented.

0 citations0 reviewsNo code linkedOpen access