@techreport(larsen, author = "Laurent Doyen and Line Juhl and Kim G. Larsen and Nicolas Markey and Mahsa Shirmohammadi", year = "2013", title = "Synchronizing Words for Timed and Weighted Automata", type = "Research Report", number = "LSV-13-15", institution = "Laboratoire Sp{\'e}cification et V{\'e}rification, ENS Cachan, France", url = "http://www.lsv.ens-cachan.fr/Publis/RAPPORTS_LSV/PDF/ rr-lsv-2013-15.pdf", note = "26~pages", ) @incollection(doyen, author = "Laurent Doyen and Thierry Massart and Mahsa Shirmohammadi", year = "2011", title = "Infinite Synchronizing Words for Probabilistic Automata", editor = "Filip Murlak and Piotr Sankowski", booktitle = "Mathematical Foundations of Computer Science 2011", series = "Lecture Notes in Computer Science", volume = "6907", publisher = "Springer Berlin Heidelberg", pages = "278--289", doi = "10.1007/978-3-642-22993-0_27", ) @article(gaubert, author = "Stephane Gaubert and Ricardo Katz", year = "2006", title = "Reachability Problems for Products of Matrices in Semirings.", journal = "IJAC", volume = "16", number = "3", pages = "603--627", url = "http://dblp.uni-trier.de/db/journals/ijac/ijac16.html#GaubertK06", ) @article(gazdag, author = "Zsolt Gazdag and Szabolcs Iv\'{a}n and Judit Nagy-Gy\"{o}rgy", year = "2009", title = "Improved Upper Bounds on Synchronizing Nondeterministic Automata", journal = "Inf. Process. Lett.", volume = "109", number = "17", pages = "986--990", doi = "10.1016/j.ipl.2009.05.007", ) @misc(Halava97decidableand, author = "Vesa Halava", year = "1997", title = "Decidable and Undecidable Problems in Matrix Theory", ) @article(Halava01mortalityin, author = "Vesa Halava and Tero Harju", year = "2001", title = "Mortality in Matrix Semigroups", journal = "AMER. MATH. MONTHLY", volume = "2001", pages = "653", ) @article(halavahirvensalo, author = "Vesa Halava and Mika Hirvensalo", year = "2007", title = "Improved matrix pair undecidability results", journal = "Acta Informatica", volume = "44", number = "3-4", pages = "191--205", doi = "10.1007/s00236-007-0047-y", ) @article(halava, author = "Vesa Halava and Mika Hirvensalo and Ronald de Wolf", year = "2001", title = "Marked \{PCP\} is decidable", journal = "Theoretical Computer Science", volume = "255", number = "1–2", pages = "193 -- 204", doi = "10.1016/S0304-3975(99)00163-2", ) @article(imreh, author = "Bal\'azs Imreh and Magnus Steinby", year = "1999", title = "Directable Nondeterministic Automata.", journal = "Acta Cybern.", volume = "14", number = "1", pages = "105--115", url = "http://dblp.uni-trier.de/db/journals/actaC/actaC14.html#ImrehS99", ) @article(kfouri, author = "D.J. Kfoury", year = "1970", title = "Synchronizing Sequences for Probabilistic Automata", journal = "Stud. Appl. Math.", volume = "49", pages = "101--103", ) @article(martyugin-bound, author = "P. V. Martyugin", year = "2010", title = "{A lower bound for the length of the shortest carefully synchronizing words}", journal = "Russian Mathematics", volume = "54", pages = "46--54", doi = "10.3103/S1066369X10010056", ) @incollection(martyugin-pspace, author = "P.V. Martyugin", year = "2010", title = "Complexity of Problems Concerning Carefully Synchronizing Words for PFA and Directing Words for NFA", editor = "Farid Ablayev and ErnstW. Mayr", booktitle = "Computer Science – Theory and Applications", series = "Lecture Notes in Computer Science", volume = "6072", publisher = "Springer Berlin Heidelberg", pages = "288--302", doi = "10.1007/978-3-642-13182-0_27", ) @book(papadimitriou, author = "Christos H. Papadimitriou", year = "1994", title = "Computational complexity.", publisher = "Addison-Wesley", ) @article(paterson, author = "M. Paterson", year = "1970", title = "Unsolvability in 3$\times $3 matrices", journal = "Studies in Applied Mathematics", volume = "49", pages = "105--107", ) @inproceedings(potapov, author = "Igor Potapov", year = "2004", title = "From Post Systems to the Reachability Problems for Matrix Semigroups and Multicounter Automata", booktitle = "Developments in Language Theory, LNCS 3340", pages = "345--356", doi = "10.1007/978-3-540-30550-7_29", ) @incollection(volkov, author = "Mikhail V. Volkov", year = "2008", title = "Language and Automata Theory and Applications", chapter = "Synchronizing Automata and the \v {C}ern\'y Conjecture", publisher = "Springer-Verlag", address = "Berlin, Heidelberg", pages = "11--27", doi = "10.1007/978-3-540-88282-4_4", )