Citation of A T



Mikhail V. Berlinkov

On the Probability of Being Synchronizable

Alg. Discr App. Math. V. 9602(2016) LNCS. 73-84,


G Saccher

Book revuews

Monatshefte für Mathematik

2015, 3(178), 489-492


V Vorel, A Roman

Complexity of road coloring with prescribed reset words

- Language and Automata Theory and Applications, Springer

LNCS, 8977(2015), 161-172, 


A Carpi, F D'Alessandro

On incomplete and synchronizing finite sets

 TCS, Elsevier, 2015


A Kisielewicz, M Szykuła

 Synchronizing Automata with Extremal Properties

- Math. Found. Comp, LNCS 9234, 331-343, 2015


A Roman, M Szykuła

Forward and backward synchronizing algorithms

 Expert Syst. Appl., 2015 - Elsevier 42, (24), 2015, 9512–9527


Tomáš Masopust, Michaël Thomazo

On the Complexity of k -Piecewise Testability and the Depth of Automata

LNCS 9168(2015), 364-376


Vladimir V. Gusev, Marek Szykuła

On the Number of Synchronizing Colorings of Digraphs

 LNCS 9223(2015) 127-139


V Vorel, A Roman

Complexity of road coloring with prescribed reset words

- Language and Automata Theory and Applications,

LNCS 8977(2015), 161-172


360. Pierre-Yves Chevalier Julien M. Hendrick, Raphael M. Jungers

Reachability of Consensus and Synchronizing Automata


JR Li, WT Zhang, YF Luo

On the finite basis problem for the variety generated by all n-element semigroups

Algebra univ., Springer, 73( 3-4), 225-248, 2015,


François Gonze, Raphaël M. Jungers, Avraham N. Trahtman

A Note on a Recent Attempt to Improve the Pin-Frankl Bound

DM & TCS, 1(17), 2015, 307-308


A Roman, M Drewienkowski

A complete solution to the complexity of Synchronizing Road Coloring for non-binary alphabets

 Information and Computation, 2015 - Elsevier


АФ Резчиков, АС Богомолов, ВА Иващенко


Надежн. Сист. Упр. 179, Саратов, 2015


Olga Sapir

Non-finitely based monoids

Semigroup Forum, 3(90), Springer, 557-586, 2015


F Gonze, RM Jungers

On the Synchronizing Probability Function and the Triple Rendezvous Time

Lang. and Aut., LNCS, 8977(2015), Springer, 212-223


A Kisielewicz, J Kowalski, M Szykuła

Computing the shortest reset words of synchronizing automata

- J. Comb. Optim.– Springer, 29(2015), 88-124


EWH Lee, WT Zhang

Finite basis problem for semigroups of order six

LMS Journal of Comput. and Math, 18(1),  2015, 1-129.


Arthur Benjamin, Gary Chartrand & Ping Zhang

The Fascinating World of Graph Theory

Popular Math.,, 360, 2015


H Fernau, P Heggernes, Y Villanger

A multi-parameter analysis of hard problems on deterministic finite automata

J. Comput.Syst. Sci.81( 2),  359-484, 2015


350. D Stoner, MC Kim

 On the Minimal Reset Words of Synchronizing Automata

2014 -


Pocci, I Demongodin, N Giambiasi.

Testing experiments on synchronized Petri nets

Aut. Sci. .Eng., IEEE Trans. 1(11), 125-138, 2014


LV Eppelbaum, I Kutasov, A Pilchin

Applied Geothermics

Lect. Notes Earth Syst. Sci., Springer, 2014, 37, No.2, 117-130.


D D'Angeli, E Rodaro

Groups and semigroups defined by colorings of synchronizing automata

 Int.J. of Algebra and Comp., World Scientific, 2014 - 2014, 9-39


C Comin

Algebraic characterization of the class of languages recognized by Measure Only Quantum Automata

 Fundamenta Informaticae,  IOS Press, 134( 3-4), 2014, 335-353



Finitely based monoids obtained from non-finitely based semigroups

- Universitatis Iagellonicae Acta Mathematica, 2014, 45-49


MV Sapir


Comb. Algebra: Syntax and Semantics,  2014 – Springer, 85-149


MV Sapir

Combinatorial algebra: syntax and semantics

Vanderbilt, 2014


N Giambiasi, C Frydman -

Timed synchronizing sequences

DEVS14, Proc.of the Symp.on Theory of Mod. & Sim. San Diego, CA, N 21. 2014


A Carpi, F D'Alessandro

Cerný-like problems for finite sets of words

ICTCS'14  Fifteenth Italian Conference. 81-92, 2014


Vladimir V. Gusev, Elena V. Pribavkina

Reset Thresholds of Automata with Two Cycle Lengths

LNCS 8587, 2014, 200-210


340. Arthur Benjamin, Gary Chartrand & Ping Zhang

The Fascinating World of Graph Theory

Princeton Univ. press, 2015  360 pp.  


Araÿÿjo, J., Cameron, P.J

Primitive groups synchronize non-uniform maps of extreme ranks             

Journal of Combinatorial Theory, Series B, 1(106), 2014, 98 – 114


Canan Güniçen, Kemal İnan, Uraz Cengiz Türker, Hüsnü Yenigün

The relation between preset distinguishing sequences and synchronizing sequences

Formal Asp. Comput. 26(2014), 1553-1667


Benz Kotzen

Novel ideas for maximising dew collection to aid plant establishment to

combat desertification and restore degraded dry and arid lands

Geophysical Research Abstracts, Vol. 16, EGU2014-1481, 2014

EGU General Assembly 2014



The  Road-Coloring Theorem..

V. XIII, Issue 2, 2014


MP Béal, D Perrin

A quadratic algorithm for road coloring

- DAM, Elsevier 2014


P. Martyugin

Computational Complexity of Certain Problems Related to Carefully Synchronizing Words for Partial Automata and Directing Words for Nondeterministic Automata

 Theory of Comput. Syst., Springer Sci.-Busyness Media, NY, 2014


Vojtěch Vorel

Complexity of a Problem Concerning Reset Words for Eulerian Binary Automata

Language and Automata Theory and Appl.  LNCS 8370, 2014.  576-587


Mikhail V. Berlinkov

Approximating the Minimum Length of Synchronizing Words Is Hard

Theor. Comput. Syst. 2(54), 211-223, 2014


NR Reilly

Regular principal factors in free objects in varieties in the interval

 [B 2, NB 2 G n] - Semigroup Forum, 2014


330.T Place, L van Rooijen, M Zeitoun

Separating regular languages by piecewise testable and unambiguous languages

- Math. Foundations of Comp. Sci. 8087,  729-740, 2013



Finitely based monoids obtained from non-finitely based semigroups

- Universitatis Iagellonicae Acta Mathematica, 2014 -


PR Jones

The semigroups B2 and B0 are inherently nonfinitely based, as restriction semigroups – Int. J.l of Alg. and Comp., 06(23), 1289-1335, 2013



F.M. Fominykh,  P.V. Martyugin , M.V. Volkov,

P (l) aying for Synchronization.

Int. J. Found. Comput. Sci. World Scientific, 6(24), 765-780,  2013.


.J. Kari, M Volkov

Cerný's conjecture and the road coloring problem

Handbook of Automata, 2013


Kisielewicz, Andrzej / Kowalski, Jakub / Szykuła, Marek

Computing the shortest reset words of synchronizing automata

 J. Comb. Optim., 1-27, 2013


Mikhail v. Berlinkov

Synchronizing quasi-eulerian and quasi-one-cluster automata

Int. J. Found. Comput. Sci., 24, , Issue 06,. 729-745 2013


Thomas Place, Lorijn van Rooijen, Marc Zeitoun

Separating Regular Languages by Piecewise Testable and Unambiguous Languages

Math. Found. of Comp. Sci. LNCS 8087, 2013, 729-740


Wojciech Czerwiński, Wim Martens, Tomáš Masopust

Separability of Regular Languages by Subsequences and Suffixes

Automata, Lang., Programming , LNCS 7966, 2013, 150-161


M Grech, A Kisielewicz

The Černý conjecture for automata respecting intervals of a directed graph

DMTCS vol. 15:3, 61–72, 2013


C Güniçen, E Erdem, H Yenigün

Generating Shortest Synchronizing Sequences using Answer Set Programming

Answer Set Programming  and Other Comput. Paradigms

6 Int. Workshop, 2013, Istanbul, Turkey


320  A Kisielewicz, M Szykuła

Generating Small Automata and the Černý Conjecture

Impl. and Appl. of Automata, LNCS ,  7982(2013),  340-348


Voynov, Andrey

Shortest positive products of nonnegative matrices

Linear Alg. and its Appl., 439 (6), 1627-1634,  2013


Araújo, João / Bentz, Wolfram / Cameron, Peter J1.

 Groups synchronizing a transformation of non-uniform kernel

 TCS, V 489, 1-9 , 2013


Ananichev, D. S. / Volkov, M. V. / Gusev, V. V.,

Primitive digraphs with large exponents and slowly synchronizing automata

Journal of Math. Sci., 192 (3), .263-278, 2013


A Kisielewicz, J Kowalski, M Szykuła

A Fast Algorithm Finding the Shortest Reset Words

LNCS,  Comput. and Comb, Springer, 7936, 2013, 182-196


G Jirásková, T Masopust –

On the State Complexity of the Reverse of   R-and  J-Trivial Regular Languages

LNCS 8031, Descr.. Compl. of Formal Syst., 2013, 136-147


  Vladimir v. Gusev,

Lower bounds for the length of reset words in eulerian automata

Int. J. Found. Comput. Sci., 24, 251 (2013).


Ondřej Klíma, Libor Polák

Alternative Automata Characterization of Piecewise Testable Languages Developments in Language Theory, LNCS Volume 7907, 2013, 289-300


P. V.  Martyugin

Careful Synchronization of Partial Automata with Restricted Alphabets

Computer Science–Theory and Appl., Springer, 76-87, 2013



310. Fernau, H., Heggernes, P., Villanger, Y.

A multivariate analysis of some DFA problems

LNCS  7810, . 275-286, 2013


Lee, Edmond W. H.

Finite Basis Problem for Semigroups of Order Five or Less: Generalization and Revisitation

Studia Logica,  101 (1), 95-115, 2013


Jorge Almeida,  Angela Cardoso

A Sequence of Weakly Monotonic Automata with Increasing Level

Int. J. Algebra, 7 ( 2),  91 – 100,  2013


Kouji Yano

Random Walk in a Finite Directed Graph Subject to a Road Coloring

J. Theoret.. Probability, 26( 1) ,  2013, 259-283



  Norman R. Reilly

Regular principal factors in free objects in Rees-Sushkevich varieties

Semigroup  Forum 86( 1), 162-182, 2013


M.V.  Sapir

Non-commutative combinatorial algebra, 2013


Carpi, Arturo ; D'ʼAlessandro,  Flavio

Independent sets of words and the synchronization problem

Advances in Applied Mathematics, V 50( 3), 339-355, 2013


Ed Dubinsky , Robin T. Wilson

High school students’ understanding of the function concept

J. of Mathematical Behavior . 32 ( 1), 2013, 83–101


Berstel, C De Felice, D Perrin, C Reutenauer…

 Recent results on syntactic groups of prefix codes

- European Journal of Comb., 7(33) , 2012, 1386–1401,



J  Dmitry S. Ananichev, Vladimir V. Gusev, Mikhail V. Volkov

 Primitive  digraphs with large exponents and slowly synchronizing automata

(Примитивные орграфы с большими экспонентами и медленно синхроизируемые автоматы)

Zapiski Nauchnyh Seminarov POMI [Komb.  Teorija Grafov. IV], 402, 9-39 (2012).



300. Krieger,  Wolfgang ; Weiss, Benjamin

 Sofic  random  processes

J. REINE UND ANGEW. MATH  671,   31-47,  2012


Igor Podolak

Klasyfikator  Hierarchiczny

 Wyd. Uniw. Jagiellońskiego,  Krakow,  2012


Edmond W. H. Lee,  Jian Rong  Li, Wen Ting Zhang

Minimal non-finitely based semigroups

Sem. Forum, 3(85),  577-580, 2012


Lee Edmond W. H

A sufficient condition for the non-finite basis property of semigroups

 Monatshefte Math. V.168, I. 3-4, 2012, 461-472



Dolinka, Igor

On free spectra of varieties of locally threshold testable semigroups

International  alg.  COMPUT. 22 (6) , 2012


Reviewer:Peter R. Jones ZBL 1234*20064, 2012

Dolinka, Igor

On free spectra of locally testable semigroup varieties.

Glasg. Math. J. 53, No. 3, 623-629 (2011).



Lee Edmond W. H

A sufficient condition for the non-finite basis property of semigroups

 Monatshefte Math. V.168, I. 3-4, 2012, 461-472


Lee, Edmond W. H.

Varieties generated by 2-testable monoids

Studia scientiarum mathematicarum hungarica, 49( 3),: 366-389   


Jane Chandlee, Jie Fu, Konstantinos Karydis, Cesar Koirala, Jeffrey Heinz, Herbert Tanner

Integrating Grammatical Inference into Robotic Planning

The 11th ICGI JMLR, Conf. Proc. 21(2012)  69–83.


Vladimir V. Gusev

Synchronizing Automata of Bounded Rank

CIAA 2012, LNCS, 7381(2012), Impl. Appl. of Automata, 171-179


290.  Fedor Fominykh, Mikhail Volkov

Playing for Synchronization

CIAA 2012, LNCS, 7381(2012), Impl. Appl. of Automata, 159-170


Pavel V. Martyugin

Synchronization of Automata with One Undefined or Ambiguous Transition

CIAA 2012, LNCS, 7381(2012), Impl. Appl. of Automata, 278-288.


Mikhail V. Berlinkov

Synchronizing Automata on Quasi-Eulerian Digraph

CIAA 2012, LNCS, 7381(2012), Impl. Appl. of Automata, 90-100


Galina Jirásková , Tomáš Masopust

On the State and Computational Complexity of the

Reverse of Acyclic Minimal DFAs

CIAA 2012, LNCS, 7381(2012), Impl. Appl. of Automata,. 229–239.


Trahtman  A.N.

 An algorithm for road coloring.

J. Disc. Alg. 213–223, 16 (2012) 


Reviewer: Alfredo Donno,  MR2884814 (2012)

 Kouji Yano, Kenji Yasutomi

Realization of an ergodic Markov chain as a random walk

subject to a synchronizing road coloring.

J. Appl. Probab. 48(2011), 3, 766–777.

Edmond W. H. Lee

Finite Basis Problem for Semigroups of Order Five or Less:

Generalization and Revisitation

Studia Logica, 2012


Kudłacik, R. Roman, A. Wagner, H.,

Effective Synchronizing Algorithms

Expert Syst. Appl., 39 (14), 11746-11757, 2012


V.Yu. Protasov,  A.S. Voynov

Sets of nonnegative matrices without positive products

Linear Alg. & Appl.,  437 (3), 749-765, 2012


Igor T. Podolak, Adam Roman, Dariusz Jędrzejczyk

Application of Hierarchical Classifier to Minimal Synchronizing Word Problem

AISC, LNCS 7267(2012), 421-429


280.  Trahtman A.N.

Some new Features and Algorithms for the Study of DFA

Open J. Discr. Math., 2(2), 2012, 45-50


Jean Berstel, Clelia De Felice, Dominique Perrin,

Christophe Reutenauer, Giuseppina Rindone

Recent results on syntactic groups of prefix codes

Europ. J. Comb., 33(7), 1386-1401,  2012


Raphaël M. Jungers

The Synchronizing Probability Function of an Automaton

SIAM J. Discrete Math. 26/1, 2012, 177-192


Adam Roman

P–NP Threshold for Synchronizing Road Coloring

Language and Automata Theory and Applications, LNCS 7183(2012), 480-489




G. Mashevitzky

Bases of identities for semigroups of bounded rank transformations of a set.

Israel J. Math., 2012,  1(191), 451-481


Khoury, Raphaël / Tawbi, Nadia

Which security policies are enforceable by runtime monitors? A survey

Comput. Sci. Review, 6 (1), 27-45, 2012


Reviewer: Marcel G. Jackson,  MR2851972(2012)

Zhang, Wen Ting(PRC-LAN); Luo, Yan Feng(PRC-LAN)

A new example of a minimal nonfinitely based semigroup.

Bull. Aust. Math. Soc. 84 (2011), no. 3, 484–491.


Kouji Yano

Random Walk in a Finite Directed Graph Subject to a Road Coloring

J. Theor. Probability, 2012, v.5.0,  2011


Wen Ting Zhang and Yan Feng Luo

 The Variety Generated by All Non-Permutative and Non-Idempotent

Semigroups of Order Four.

Proc. The Int. Conf. Algebra 2010: Indonezia, World Sci. (2011), 721-735.


Brian Marcus.

Symbolic Dynamics.  Math. of Complexity and Dynamical

Systems. 2011, 1689-1710.


270. E. W. H. Lee, Jlan Rong Li

Minimal non-finitely based monoids


475, Warshawa, 2011, 65


Wen Ting Zhang, Yan Feng Luo

A new example of a minimal nonfinitely based semigroup

 Bull. of the Austr. Math. Soc., 3(84), Cambr. Univ Press, 2011, 484-491


MV Volkov, SV Goldberg, and SI Kublanovsky

A minimal nonfinitely based semigroup whose variety

Is polynomially recognizable
J. of Mathematical Sciences,. 6(177), 2011, 847-859


I. Dolinka

On free Spectra  of Locally Testable Semigroup Varieties

Glasgow Math. J., 53 (2011), 623–629.


V  Kouji Yano and Kenji Yasutomi

Realization of an ergodic Markov chain as a random walk subject

 to a synchronizing road coloring.

J. Appl. Probab. V. 48, 3 (2011), 766-777.


Vladimir V. Gusev

Lower Bounds for the Length of Reset Words in Eulerian Automata

Lect. Notes in Comput, Sci., 6945(2011), Reachability Problems, 180-190


E. W. H. Lee

A sufficient condition for the non-finite basis property of semigroups

Monatshefte für Mathematik, 2(83),  2011 250-280


Trahtman A.N.

An Algorithm for Road Coloring.

Lect. Notes in Comp. Sci, Springer, 7056 (2011), Springer, 349--360


Ishanu Chattopadhyay, Yicheng Wen, Asok Ray, Shashi Phoha

Unsupervised Inductive Learning In Symbolic Sequences via Recursive

Identification of Self-Similar Semantics.  

American Control Conference, CA, USA, 2011, 125-130


М. В. Берлинков

О погрешности полиномиального вычисления оптимальной

раскраски графа в синхронизируемый автомат

(On the error of polynomial computations of optimal

 graph coloring in a synchronized automaton)

Прикл. дискр мат. (Appl. disc. math.)

2011, № 2, 49–72


260. Benjamin Steinberg

The Černý conjecture for one-cluster automata with prime length cycle.

Theoret. Comput., Sci., 412(39), 5487-5491, 2011


B. A. Davey, M. G. Jackson, J. G. Pitkethly and C. Szabó

Finite degree: algebras in general and semigroups in particular

Semigroup Forum, V. 83, 1(2011), 89-110


Simon M. Goberstein

Lattice isomorphisms of bisimple monogenic orthodox semigroups

Semigroup Forum, 2011, 2(83), 250-280


Trahtman A.N.

Modifying the upper bound on the length of minimal synchronizing word.

 Lect. Notes in Comp. Sci, Springer, 6914(2011), 173-180


Lee EWH, Volkov MV

 Limit Varieties generated by completely 0-simple Semigrouos

Int. J. of Alg. and Comput.,  21(1-2),   257-294,   2011


Luo, Yanfeng / Zhang, Wenting,

On the variety generated by all semigroups of order three

 J. of Algebra, 334(1), 1-30, 2011


Beal MP, Berlinkov MV, Perrin D

 A quadratic upper bound on the size of a synchronizing word

In one-cluster automata Int. J Found. Comput. Sci. 22(2), 277-288, 2011



Berwick, Robert C. , Okanoya, Kazuo , Beckers, Gabriel J.L, Bolhuis, Johan J.

  Songs to syntax: the linguistics of birdsong.

Trends in Cognitive Sciences, V 15, I 3, 113-121, 2011


K.Chmiel, A.Roman

COMPAS - A Computing Package for Synchronization

LNCSImpl. and Appl. of Automata, , 6482(2011), 79-86 2011


G. Budzban and Ph. Feinsilver

The generalized road coloring problem and periodic digraphs

Applicable Algebra in Engineering, Communication and Computing, 2011

 V 22, N 1,  2011, 21-35


250. E.W.H. Lee

Finite basis problem for 2-testable monoids

Centr. Eur. J. of Math,. Vol. 9, N 1, 2011, 1-22


Goran Hognas, Arunava Mukherjea

Probability Measures on Semigroups

Convolution Products, Random Walks and Random Matrices

Probability and Its Applications, Springer, 2011, 1-62


 Roman, Adam

The NP-completeness of the Road Coloring Problem

 Information Processing Letters, 111 (7), .342,  2011


Tim Boykett

Aesthetic and Mathematical Research: A Comparism with two Examples

Proceedings of Bridges 2010: Math, Music, Art, Arch., Culture (2010)



 Kudryavtseva G.

Ordered semigroups, upper-triangular reflexive relations and semigroups of languages.

 IJAC 6, 20(2010), 823–832.


Roman A.

Experiments on Synchronizing Automata

Schedae Informaticae, Versita, Warsaw, V. 19, 35-51, 2010


MV Volkov, SV Goldberg S. I. Kublanovsky

A minimal nonfinitely based semigroup whose variety is polynomially recognizable


Минимальная бесконечно базируемая полугруппа

с полиномиально распознаваемым многообразием)

Фунд. и прикл.мат., 16, 3(2010), 105—122.




RM Jungers

The synchronizing probability function of an automaton
JM2010 . LNCS, 6072:37–47, 2010.


M. Jackson and M. Volkov

The Algebra of  Adjacency Patterns: Rees Matrix Semigroups with Reversion

Fields of Logic and Computation

LNCS  Volume 6300( 2010), 414-443,


Benjamin Steinberg

A Theory of Transformation Monoids:

Combinatorics and Representation Theory

The Electronic Journal of Combinatorics,  v.17,  i. 1,   2010, 3-56


240.  Arturo Carpi, Flavio D'Alessandro

Locally strongly transitive automata and the Hybrid Cerny-Road coloring problem

12-th ICTCS, Camerino, Italy, 2010


James Rogers, Jeffrey Heinz, Gil Bailey, Matt Edlefsen and Molly Visscher, et al.

On Languages Piecewise Testable in the Strict Sense

LNCS, 6149(2010),  MOL, 255-265


Dmitry Ananichev, Vladimir Gusev, Mikhail Volkov

Slowly Synchronizing Automata and Digraphs

LNCS 6281(2010), MFCS 2010, 55-65


Graph Coloring: Four Color Theorem, Acyclic Coloring, List Coloring, Chromatic Polynomial,  Equitable Coloring, Hadwiger Conjecture

Life Journey 2010, 170


Israeli Mathematicians: Adi Shamir, Giulio Racah, Saharon Shelah, Zlil Sela, Robert Aumann,

Michael O. Rabin, Oded Schramm, Avraham Trahtman

Books LLC, 176, 2010


Yuri. Gulak,

On Elementary and Algebraic Cellular Automata

Unifying Themes in Complex Systems, Proc.of the Sixth Int. Conf., P.1, Ch. 7, 2010, 50-57



 Factorial, Binomial Coefficient, Combinatorics, Permutation,

Combination, Pigeonhole Principle, Catalan's Constant

Books LLC, Barnes & Noble, 612, 2010


I. Woungang, S. Misra and S. Chandra Misra

Selected Topics in Information and Coding Theory

Series on Coding Theory and Cryptology, v. 7, World Scientific, Singapore, 2010


Automata Theory: Finite- State Machine, Regular Expression, Pushdown Automaton,

Star Height Problem, Tree Automaton, Sequential Logic,  Books LlC,  290,  2010


Mathematics and Culture: Leonardo Da Vinci, Arcadia, Magic Square,

 Mathematical Folklore, Danica Mckellar, Proof, Mathematics and Art, Numbers

Books LlC,  846,  2010


230. S. Shin, J. Yoo 

A note on the rank of semigroups

Semigroup Forum V 81, N 2, 335-343, 2010


 Jean berstel, dominique perrin, christophe reutenauer

Codes and Automata,

Cambridge University Press, 2010, 620


Lambert M Surhone, Miriam T. Timpledon, Susan F Marseken 

Road Coloring Problem .

VDM Verlag Dr. Mller AG & Co. Kg,  2010, 76


M. Berlinkov

On a Conjecture by Carpi and D'Alessandro

 Developments in Language Theory, Springer, NY, 

 LNCS 6224, 2010,  66-75


B. Steinberg

The Averaging Trick and the Cerny Conjecture

- Developments in Language Theory, Springer, NY, 

 LNCS 6224, 2010, 423-431


A Carpi, FD'Alessandro

On the Hybrid Cerny-Road Coloring Problem and Hamiltonian Paths

- Developments in Language Theory, Springer, NY, 

 LNCS 6224, 2010, 124-135


George G. Szpiro

A Mathematical Medley: Fifty Easy Pieces on Mathematics

AMS Bookstore, 2010, 236


Trahtman A. N.

A Partially Synchronizing Coloring

CSR-2010,  Lecture Notes in Computer Science 6072, Springer, 2010, 362-370

Trahtman A.N., Bauer T., Cohen N.

Linear visualization of a Road Coloring.

9th Twente workshop on graphs and Comb. Optim., Cologne 2010, 13-16


N Karimi

Synchronizing Coloring Of A Directed Graph
 Proc. of the IMECS 2010, Hong Kong,, Vol III, 1-5


Gary Chartrand, Linda Lesniak, Ping Zhang

Graphs & Digraphs, Fifth Edition

 Taylor@Francis  group, Chapman & Hall , 2010, 480p.

 220. A Cerna, J Cerny
Position Identification of Moving Agents in Networks
. Acta Polytechnica Hungarica Vol. 7, No. 2, 2010. 5 -23.

Charles C. Edmunds, Edmond W. H. Lee and Ken W. K. Lee
Small Semigroups Generating Varieties with Continuum Many Subvarieties
 Order, V.27, N1 . Springer, 2010, 83-100 


  Budzban G., Feinsilver P.

An approach to road coloring problem based on vector spaces.

(Подход к задаче раскраски дорог, основанный на векторных пространствах

Zvestiya vysshikh uchebnykh zavedenii  Math., 2010, N 1, 10–15

D.S. Ananichev 

The threshold of avoidance of partially monotonic automata

(Порог аннуляции для частично монотонных автоматов)

Izvestiya vysshikh uchebnykh zavedenii Math
2010, N 1,  1–9


Steinberg B.
Cerny’s conjecture and group representation theory
 Journal of Algebraic Combinatorics, v. 31,  1 ( 2010 ), 83-109



范晓伟, 吴玉杰, 周义德 - 节能技术, 2009


Steinberg B

A Theory of Transformation Monoids: Combinatorics and Representation Theory

ELECTRON. J. COMB.   V 17(1), 2010, 3-56


  Meena  Mahajan,  B. V. Raghavendra Rao 

Small-space analogues of Valiant's classes

FCT'09, Proceedings of the 17th int. conf, on Fund.. comput. theory 

Springer-Verlag Berlin, Heidelberg , 2009


 Riccardo Dondi

The longest haplotype reconstruction problem revisited

FCT09, 109-120, 2009


210. B. Marcus

Symbolic Dynamics. Encyclopedia of Complexity and Systems Science

Springer, New York, 2009, 8888-8910



Complexity of problems concerning reset words for some partial cases of automata

Acta Cybernetica , V 19,  Issue 2,  2009 , 517-536  


Arturo Carpi, Flavio D’Alessandro

Strongly transitive automata and the Cerny conjecture

Acta Informatica, V 46, 8(2009), 591-607.


B Steinberg

The averaging trick and the Cerny conjecture
Trans. Amer. Math. Soc. 361 (2009), 1429–1461.


A. Bogomolny, The Lighter Side of Mathematics,

R.K Guy and R.E.Woodrow, eds. 2009

Biskup, M.T.  Plandowski, W. ,

Shortest synchronizing strings for Huffman codes

Theoretical Computer Science, 410 (38),  3925-3941,  2009


  A Carpi, FD'Alessandro

The Synchronization Problem for Locally Strongly Transitive Automata
34th International Symposium, MFCS 2009, LNCS 5734 (2009) - Springer. 211–222


Ewh lee

combinatorial rees–sushkevich varieties that are cross,

finitely based, or small
 - bulletin of the australian mathematical society, 2009


  James Rogers, Jeffrey Heinz, Gil Bailey, Molly Visscher, David Wellcome,

Matt Edlefsen, and Sean Wibel.

On Languages Piecewise Testable in the Strict Sense.

Proceedings of the 11th Meeting of the Association of Math.of Language. 2009


Rauff, James V

Way back from anywhere: exploring the road coloring conjecture, 

Mathematics and Computer Education. 01, 2009.


 J Almeida, B Steinberg

Matrix Mortality and the Cerny-Pin Conjecture
 Germany,  DLT 2009,  LNCS 5583( 2009), 
Springer Monographs in Mathematics. Springer,  67-80


200. MP Beal, D Perrin

A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata
 Germany, DLT,  Springer Monographs in Mathematics. Springer,  81-90, LNCS 5583( 2009)


Trahtman A.N.

The road coloring problem.

 Israel Journal of Math. , 172(1), 51-60, 2009


Jurgen Bang-Jensen, Gregory Gutin
Digraphs: Theory, Algorithms and Applications.

Springer Monographs in Mathematics, 2-nd edition, 2009

M.V. Volkov

Synchronizing automata preserving a chain of partial orders
TheoreticalComputerScience  410 (37),  3513-3519, (2009)


Roman A.

Decision Version of the Road Coloring Problem is NP-complete,

LNCS 5699 (2009) 287-297


  Peter M Neumann

Primitive permutation groups and their section-regular partitions
Michigan Math. J. ,V.58, Issue 1, 309-322. 2009


Shevrin L.N., Vernikov B.M., Volkov M.V.

Lattices of semigroup varieties


53, N 3, 3–36, (Russian) 2009


  J. Berstel, D. Perrin, C. Reutenauer

Codes and automata

Version 14,  2009


Roman A

Genetic Algorithm for Synchronization
LNCS 5457, 684-695, 2009


 Dolinka I.

A class of inherently nonfinitely based semirings
 Algebra Univ., 60(1), 19-35, 2009

190.  Roman A

Synchronizing finite automata with short reset words
(ICCMSE 2005), , 2005 Corinth, GREECE
Applied mathematics and computation, Is. 1, 125-136, 209(2009 )

Reilly NR

Shades of orthodoxy in Rees-Sushkevich varieties

 Semigroup forum   V 78 1, 157-182,    2009


 M Boyle 

Geometric and probabilistic structures in dynamics:

Contemporary Mathematics V. 469, 2008, 70-96

Edward P. Stabler

Computational Linguistics: Language Learning



Gulak Yu.

On Elementary and Algebraic Cellular Automata

 Unifying themes in Compl. syst., Proc of 6-th conf, NECS,

v. 6, Springer, 50-57, 2008


M V. Volkov

Synchronizing automata and the Černý conjecture

 Language and automata theory and applications, 2008 - Springer

 LNCS 2008 5196/2008, 11-27,


 Volkov M.V.

Synchronizing Automata and the Road Coloring Theorem

Russian-Indian Workshop on Algebra, Combinatorics and Complexity

(a satellite workshop of the 3rd International Computer Science Symposium in Russia),

Moscow, Russia, 2008


Volkov M.V.

Synchronizing Strongly Connected Digraphs

AutoMathA Brainstorming and Cooperation Days, Wroclaw, Poland, 2008


 Reilly NR

Varieties generated by completely 0-simple semigroups.

J. Aust. Math. Soc. 84 (2008), no. 3, 375--403.


  Trahtman A.N.

Road Coloring Problem. Implementation and Visualization of the Algorithm.

Proc. of  AMS-SMS joint meeting, Shanghai, 2008, 109-110.


180. Reilly NR
The interval [B-2, NB2] in the lattice of Rees-Sushkevich varieties
ALGEBRA UNIVERSALIS, v. 59:(3-4), 345-363, 2008

  Reviewer: Marcel G. Jackson MR2337869 (2008h:20080)
   Kamilla Katai-Urban, Csaba Szabo
On the free spectrum of the variety generated by the combinatorial

completely 0-simple semigroups.

Glasgow Math. J., 49, 1:, 93-98, 2007, 20M07(08B20)


G Chartrand, P Zhang 

Chromatic Graph Theory
series DISCR. MATH. & ITS APPL., CRC Press, 2008


Volkov MV

Synchronizing Automata and the Cerny Conjecture.
 Lang.& Aut. Theory & Appl. 2-d Int.Conf., Lata, Spain,  2008,

Springer,  LNCS 5196, 11-27, 2008

Boyle M

Open Problems in Symbolic Dynamics

Geom. & prob. struct. In dynamics: CONT. MATH. SER. v. 469, 69-118, 2008


A. Carpi, FD'Alessandro

The Synchronization Problem for Strongly Transitive Automata.
12th Int. Conf. DLT, Kyoto, LNCS 5257, 240-251, 2008 


 Reilly NR

Varieties generated by completely 0-simple semigroups

 J. of the Australian Math. Soc., Cambridge Univ Press - 84,  375-403, 2008


Combinatorial Rees-Sushkevich varieties are finitely based.
Int. J. ALG. AND COMPUT.  V. 18   Issue: 5   957-978,  2008


 Lee EWH,  Reilly NR
Centrality in Rees-Sushkevich varieties

 Algebra Universalis, 2(58), 2008


  Hermiller S, Holt DF, Rees S

Groups whose geodesics are locally testable.
J. ALG. AND COMPUT.  V. 18   Issue: 5   911-923,  2008

170.M.P.Beal, J.Berstel, B Marcus, D Perrin, Christophe Reutenauer, Paul H. Siegel

Length Codes and Finite Automata

World Sci. 2008


 Martyugin, P.V.

Series of slowly synchronizing automata with a zero state over a small alphabet 
Information and Computation. v. 206, Iss. 9-10, 1197-1203, 2008.

Jurgensen Helmut,


Information and Computation. v. 206, Iss. 9-10.1033-1044, 2008.


  Trahtman A.N.
The Road Coloring and Cerny Conjecture.
 Proc. of Prague Stringology Conference. 1-12,  2008.

Trahtman A.N.

Synchronizing Road Coloring.

5-th IFIP WCC-TCS, Springer, , 43-53, 273(2008).


 Marek Tomasz Biskup 

Shortest Synchronizing Strings for Huffman Codes.

L NCS. 120--131, MFCS 2008, 5162(2008)

 Ezek Jaroslav.

Universal Algebra. 2008


 Talhi, C. / Tawbi, N. / Debbabi, M.

Execution monitoring enforcement under memory-limitation constraints ,
  Information and Computation, 206 (2),  158-184, 2008

Kublanovsky S. I., Lee Edmond W. H., Reilly  Norman R.
Some conditions related to the exactness of Rees-Sushkevich varieties

Semigroup Forum,  76(1), 87-94, 2008


Sasikala, K.; Dare, V. R.; Thomas, D. G.PUB.

Learning of Partial Languages

SOURCE Engineering Letters;  2( 14 ),  72, 2007



 160. Sharan, G.; Beysens, D.; Milimouk-Melnytchouk, I.

A study of dew water yields on Galvanized iron roofs in Kothara (North-West India)

Journal of Arid Environments, V. 69, I. 2, 259-269, 2007


 Jacobs, A.F.G.; Heusinkveld, B.G.; Berkowicz, S.M.

Passive dew collection in a grassland area

Atmospheric Research 87 (2007), 3-4. 377 - 385.


  EWH Lee,  MV Volkov

The structure of the lattice of combinatorial Rees-Sushkevich varieties

Proc of Conf. Semigroups & Formal Lang. Portugal, World Sci.   164-187, 2007


Mashevitzky G.

A new method in the finite basis problem with applications to rank 2

transformation semigroups

INT.J. OF ALG. AND COMPUT. 17 (7): 1431-1463, 2007


 Lee Edmond. W. H.



 Internat. J. Algebra Comput., 17(8), 1553 - 1572, 2007  

Reilly N.R.
Complete congruences on the lattice of Rees-Sushkevich varieties
COMMUNICATIONS IN ALGEBRA 35 (11): 3624-3659, 2007

Volkov MV.
Synchronizing automata preserving a chain of partial orders

CIAA 2007, Prague,  LECT. NOTES IN COMPUT. SCI. 4783, 27-37, 2007

Lee Edmond W. H.

On a Simpler Basis for the Pseudovariety EDS 

 Semigroup Forum,  75 (2):  477-479, 2007


  Kamilla Katai-Urban, Csaba Szabo

On the free spectrum of the variety generated by
the combinatorial completely 0-simple semigroups

Glasgow Math.  J., 49, 1:,  93-98, 2007


     Ananichev DS, Volkov MV, Zaks YI.
Synchronizing automata with a letter of deficiency 2. 

Theoretical computer science, 376, 1-2, 30-41, 2007

150.  Trahtman A. N.

Synchronization of some DFA,



 Lee E.W.H. ,

On the complete join of permutative combinatorial Rees-Sushkevich varieties, 
Int. Journal of Algebra 1, 1-9. 2007


 Adam Roman
Two simple methods for obtaining new classes of automata
fulfilling Cerny Conjecture

Schedae Informaticae, 16 (2007), 35-46.


I. Yu. Simonenko

On border relations on finite automata

Proceedings of  Int. Conf. Intellect Systems and Comp. Sci. MGU, 2006


Tzivion S. , Eppelbaum L
Water Production Using Air Cooling Under Conditions of Some World Coastal Regions
Proc. of First Int. Conf. IDP, Sede Boker, 2006, 139

 L Kontorovich, C Cortes, M Mohri

Learning linearly separable languages
 Lecture Notes in Computer Science,  4264(2006), 288-303


C Talhi, N Tawbi, M Debbabi

Execution monitoring enforcement for limited memory systems

Proc. of the 2006 Int. Conf. on Privacy, Security and Trust,

ACM Int.Conf.Proc. Series; V 380, 2006


 Mazurov V.D., Khukhro E.I.

Unsolved problems in the theory of groups

Kourovka notes, Novosibirsk, 2006 (Russian)


Adam Roman
Merging states and synchronization problem
Schedae Informaticae 15 (2006), 95-108

 Reviewer: Marcel G. Jackson, MR2228521 (2007c:20130)
Lee, Edmond W. H.

Subvarieties of the variety generated by the five-element Brandt  semigroup.

Int. J. Algebra Comput. 16 (2006), no. 2, 417--441.  20M07


140  Reviewer: I. Kozhukhov, Ref J Mat. (2006 .12-13-A06.152)

12 63, no. 2, 171--173 , 2006

Popov V. Yu.  

On the property of having an independent basis in semigroup varieties.
(Russian) Algebra Logika 44 (2005), 1, 81--96


  Gulak Yu.
Algebraic Properties of Elementary Cellular Automata
 Wolfram science conf. NKS 2006, Washington, 2006

Ananichev DS, Volkov MV, Zaks YI.
Synchronizing automata with a letter of deficiency 2 
lecture notes in computer science 4036: 433-442 2006

Lee, E.W.H.
Subvarieties of the variety generated by the five-element Brandt semigroup
 International Journal of Algebra and Computation 16 (2), 417-441. 2006
 del Campo, A.D., Navarro, R.M., Aguilella, A., Gonza?lez, E.
Effect of tree shelter design on water condensation and run-off and
its potential benefit for reforestation establishment in semiarid climates 

Forest Ecology and Management 235 (1-3), 107-115, 2006

Trahtman A.N.
An efficient algorithm finds noticeable trends and examples concerning the Cerny conjecture

Trahtman A. N.
Notable trends concerning the synchronization of graphs and automata.
El. Notes in Discrete Math., CTW06, Vol. 25, 173-175, 2006  

 Wang RH, Zhang HZ, Huang Q
Characteristics and laws of MODS coupling relation in and zone
 under global change 

CHINESE SCIENCE BULLETIN 51: 75-81 Suppl. 2006  
D. Beysens, I. Milimouk, V.S. Nikolayev, S. Berkowicz, M. Muselli,
    B. Heusinkveld and A.F.G. Jacobs
Comment on - "The moisture from the air as water resource in arid region:
 Hopes, doubt and facts" - by Kogan and Trahtman 


130.   Kogan B., Trahtman A.N.
Response - Comment on - "The moisture from the air as water resource in
arid region: Hopes, doubt and facts" - by Beysens et al


Vazquez A, Arias J, Sanchez RM
Calcite and hematite minerals: a promising application as dew water collectors 

Seif S, Szabo C
Computational complexity of checking identities in 0-simple semigroups
 and matrix semigroups over finite fields 

SEMIGROUP FORUM 72 (2): 207-222 MAR-APR 2006  

   Muselli M, Beysens D, Millmouk I
A comparative study of two large radiative dew water condensers



M Broy