PAPERS

 

pdf file  

dvi file  

Some new Features and Algorithms for the Study of DFA

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

 

pdf file  

dvi file  

ps file  

An Algorithm for Road Coloring. Lect. Notes in Comp. Sci, 7056 (2011), Springer, 349--360

 

pdf file  

dvi file  

ps file  

Modifying the Upper Bound on the Length of Minimal Synchronizing Word. Lect. Notes in Comp. Sci, 6914(2011) Springer, 173-180

pdf file

dvi file

postscript file
A Partially Synchronizing Coloring.. CSR 2010, Lect. Notes in Comp.  Sci, 6072(2010) , 363-370
  

pdf file
dvi file
postscript file
The road coloring problem, Israel J. of Math. , 172(1),  2009, 51-60

pdf file
dvi file

The Road Coloring and Cerny Conjecture. Proc. of PSC. Prague,  2008, 1-12. 

pdf file

dvi file
 Synchronizing Road Coloring. IFIP, Springer, WCC-TCS 2008, 273(2008), 43-53

 

dvi file
pdf file
postscript file
Synchronization of some DFA. Lect. Notes in Comp. Sci, Springer, TAMC 2007, 4484(2007), 234-243 (improved version)

 

pdf file
dvi file

postscript file

   The Černę Conjecture for Aperiodic Automata.  Discr. Math. & Theoret. Comput. Sci. v. 9, 2(2007), 3-10

mht file
Word file
Response to the comment on “The moisture from the air as water resource in arid region: Hopes, doubt and facts” by Beysens et al. With B. Kogan, Journal of Arid Environments 2, 67(2006), 353-356.

pdf file
Notable trends concerning the synchronization of graphs and automata. El. Notes in Discr. Math., 25(2006), 173-175

dvi file
postscript file
pdf file
An efficient algorithm finds noticeable trends and examples concerning the Cerny conjecture. Lect. Notes in Comp. Sci, Springer, MFCS 2006, 4162(2006), 789-800.

dvi file
postscript file
pdf file
Reducing the time complexity of testing for local threshold testability. Theoret. Comput. Sci., 328(2004), 151-160.


tex file
dvi file
postscript file
Verification of algorithms for checking some kinds of testability. In Algebraic Methods in Language Processing, TWLT 21, eds. F.Spoto, G. Scollo, A. Nijholt. 2003, 253-263.


tex file
dvi file
postscript file
.Reducing the time complexity of testing for local threshold testability, Lect. Notes in Comp. Sci, 2759(2003), 141-148.


tex file
dvi file
postscript file
A package TESTAS for checking some kinds of testability. Lect. Notes in Comput. Sci., 2608(2003), 228-232.


tex file
dvi file
postscript file
A polynomial time algorithm for left [right] local testability. Lect. Notes in Comput. Sci., 2608(2003), 203-212.


tex file
dvi file
postscript file
Identities of locally threshold testable semigroups, in C. Martin-Vide & V. Mitrana, eds, Grammars and Automata for String Processing: from Mathematics and Computer Science to Biology, and Back. Taylor and Francis, London, 2003, 347-356.


dvi file
tex file
postscript file
pdf file
The Moisture from the Air as Water Resource in Arid Region: Hopes, Doubts and Facts, with B Kogan. Journal of Arid Environments, London. vol. 2, 53(2002), 231-240


tex file
dvi file
postscript file
An algorithm to verify local threshold testability of deterministic finite automata, Lect. Notes in Comp. Sci. 2214(2001), 164-173.


tex file
dvi file
postscript file
Algorithms verifying local threshold and piecewise testability of semigroup and solving Almeida problem. in T. Imaoka eds., Alg. semigroups, formal languuges and computation. RIMS Kokyuroku Proceedings, 1222(2001).

pdf file
dvi file
postscript file
Piecewise and local threshold testability of DFA. Lect. Notes in Comp. Sci, 2138(2001), 347-358, 13 Int. Symp. on Fund. of Comput. Theory., Riga, Latvia, Aug. 2001..


tex-file
dvi file
postscript file
. Algorithms finding the order of local testability of deterministic finite automaton and estimation of the order. Theoret. Comput. Sci., 235(2000), 183-204.


tex file
dvi file
postscript file
Precise estimation on the order of local testability of deterministic finite automaton, Theoret. Comp. Sci. 231(2000), 59-74.

tex file
dvi file
postscript file
The identities of k-testable semigroups, Comm. in algebra, v. 27, 11(1999), 5405-5412.

tex file
dvi file
postscript file
Optimal estimation on the order of local testability of deterministic finite automaton, Lect. Notes in Comp. Sci, 1436(1998), 198-212.

tex file
dvi file
postscript file
A polynomial time algorithm for local testability and its level, Int. J. of Algebra and Computing, v. 9, 1(1998), 31-39.

 tex file
dvi file
postscript file
Identities of a five-element 0-simple semigroup, Sem. Forum, v. 48, NY, 1994, 385-387.

 

Some Reports

 

 

pdf file
 dvi file

Linear visualization of a Road Coloring. 9 Cologne Twente workshop on graphs and Comb. Optim., Cologne 2010, 13-16 (with Bauer T., Cohen N.)

 

Road Coloring Problem. Implementation and Visualization of the Algorithm. AMS-SMS joint meeting, Shanghai, Dec. 2008, 109-110.

pdf file
dvi file

 Synchronizing Road Coloring.  World Computer Congress, 5-th Int.Conf. on Theoret. Comput. Sci., Milan, Italia, September, 273(2008), 43-53.

 

pdf file
dvi file

The Road Coloring and Cerny Conjecture. Prague Stringology Conference. Prague, Czechia, September, 2008, 1-12. 

 

 Some aspects of Synchronizing Road Coloring. Workshop "Around the Cerny conjecture". Wroclaw, Poland, June, 2008.

 The implementation of the Algorithm of Road Coloring. 12-th Mons Theoret, CS Days. Mons, Wallonie, August, 2008.

 

The Road Coloring Problem. Algebraic aspects of the Proof and Corresponding Algorithms. Annual Meeting of IMU,

Alg. Comb. and Graph Theory. Ashkelon, Israel, May, 2008.

dvi file

The visualization of digraph based on its structure properties. with T. Bauer, N.Cohen. Conf.  RTAGS, Ramat-Gan, Israel, December , 2007.

 

Synchronization of some DFA, Shanghai, 4th Annual Conf. on Theory and Appl. of Models of Comput, May, 2007

 

dvi file
An efficient algorithm finds noticeable trends and examples concerning the Cerny conjecture. 31st Int. Symp. on Math. Found. of Comput. Sci. Bratislava, Aug. 2006.

 

pdf file
Notable trends concerning the synchronization of graphs and automata. Cologne-Twente Workshop on Graphs and Comb. Opt., Lambrecht, Germany, June 2006.

pdf file
dvi file
Some results of implemented algorithms of synchronization. 10-th Journees Montoises d'Inform. Theor., LIege, Belgia, September 8-11, 2004

pdf file
dvi file
Cerny conjencture for DFA accepting star-free languages. ICALP, Workshop on synchronizing automata, Turku, Finland, July 16, 2004

dvi file
Graph representation for locally testable automata and generalizations. Algorithms and programs. Third Haifa Workshop on Interdisciplinary Appl. of Graph Theory, Combinatorics and Algorithms, Haifa, Israel, May 27-29, 2003.

tex file
dvi file
postscript file
The Existence of Synchronizing Word and Cerny Conjecture for Some Finite Automata. Second Haifa Workshop on Graph Theory, Combinatorics and Algorithms, Haifa, Yune 17-20, 2002.

dvi file
postscript file
A package for checking some kinds of testability. with D. Belostotski, D. Kravtsov, A. Shemshurenko, M. Sobol, Sh. Yakov, 6-th Int. Conf. on Impl. and Appl. of Automata, CIAA2001, Pretoria, South Africa, July 23-27, 2001.

dvi file
postscript file
Locally, locally threshold and piecewise testable languages. Some implemented algorithms. with D. Belostotski, D. Kravtsov, A. Shemshurenko, M. Sobol, Sh. Yakov, Discrete Math. and Theor. Comput. Sci., Constanca, Romania, 2-6 July, 2001.


tex file
dvi file
postscript file
Verifying piecewise testability of deterministic finite automaton. Fifth International Conference on Implementation and Application of Automata, CIAA2000, London, Ontario, Canada, Yuly 24-25, 2000.


tex file
dvi file
postscript file
Locally threshold testable semigroups, International Conference on Semigroups, Braga, Portugal, June 18-23, 1999

txt file
Atmospheric precipitation as water resource. with B.Kogan. The 7-th International conference on Environmental Challenges for the Millenium. Jerusalem, Israel, Yune 13-18, 1999.

dvi file
postscript file
Precise upper bound of the order for local testability. Lectures of abstracts, Semigroups and application, Conf. St. Andrew, Scotland, July 2-9, 1997.



 

 

 

SUBMITTED, ACCEPTED

 

 

 

 

 

CITATION of the publications



htpp://www.cs.biu.ac.il/~trakht