☰

Jeff Shallit - Publications

Affiliations: 
University of Waterloo, Waterloo, ON, Canada 
Area:
Computer Science
Tree Info Similar researchers PubMed Report error

44 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2016 Holub Š, Shallit J. Periods and borders of random words Leibniz International Proceedings in Informatics, Lipics. 47. DOI: 10.4230/LIPIcs.STACS.2016.44  0.356
2016 Forsyth M, Jayakumar A, Peltomäki J, Shallit J. Remarks on Privileged Words International Journal of Foundations of Computer Science. 27: 431-442. DOI: 10.1142/S0129054116500088  0.412
2016 Bright C, Devillers R, Shallit J. Minimal Elements for the Prime Numbers Experimental Mathematics. 25: 321-331. DOI: 10.1080/10586458.2015.1064048  0.311
2015 Du CF, Shallit J, Shur AM. Optimal Bounds for the Similarity Density of the Thue-Morse Word with Overlap-Free and 7/3 -Power-Free Infinite Binary Words International Journal of Foundations of Computer Science. 26: 1147-1165. DOI: 10.1142/S012905411540016X  0.349
2015 Guo C, Shallit J, Shur AM. Palindromic rich words and run-length encodings Information Processing Letters. DOI: 10.1016/j.ipl.2016.07.001  0.394
2015 Mousavi H, Shallit J. Mechanical proofs of properties of the Tribonacci word Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 9304: 170-190. DOI: 10.1007/978-3-319-23660-5_15  0.314
2015 Bell PC, Reidenbach D, Shallit J. Factorization in formal languages Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 9168: 97-107. DOI: 10.1007/978-3-319-21500-6_7  0.42
2014 Du CF, Shallit J. Similarity density of the Thue-Morse word with overlap-free infinite binary words Electronic Proceedings in Theoretical Computer Science, Eptcs. 151: 231-245. DOI: 10.4204/EPTCS.151.16  0.387
2013 Mousavi H, Shallit J. Filtrations of formal languages by arithmetic progressions Fundamenta Informaticae. 123: 135-142. DOI: 10.3233/FI-2013-804  0.456
2013 Charlier E, Domaratzki M, Harju T, Shallit J. Composition and orbits of language operations: finiteness and upper bounds International Journal of Computer Mathematics. 90: 1171-1196. DOI: 10.1080/00207160.2012.681305  0.398
2013 Tan S, Shallit J. Sets represented as the length-n factors of a word Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8079: 250-261. DOI: 10.1007/978-3-642-40579-2-26  0.313
2013 Mousavi H, Shallit J. Shortest repetition-free words accepted by automata Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8031: 182-193. DOI: 10.1007/978-3-642-39310-5_18  0.363
2012 Rampersad N, Shallit J, Xu Z. The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages Fundamenta Informaticae. 116: 223-236. DOI: 10.3233/FI-2012-680  0.414
2011 Bugeaud Y, Krieger D, Shallit J. Morphic and automatic words: Maximal blocks and Diophantine approximation Acta Arithmetica. 149: 181-199. DOI: 10.4064/aa149-2-7  0.338
2011 Rampersad N, Shallit J, Wang MW. Inverse star, borders, and palstars Information Processing Letters. 111: 420-422. DOI: 10.1016/J.Ipl.2011.01.018  0.482
2011 Alpoge L, Ang T, Schaeffer L, Shallit J. Decidability and shortest strings in formal languages Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6808: 55-67. DOI: 10.1007/978-3-642-22600-7_5  0.355
2011 Demaine ED, Eisenstat S, Shallit J, Wilson DA. Remarks on separating words Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6808: 147-157. DOI: 10.1007/978-3-642-22600-7_12  0.315
2011 Shallit J. Fife's theorem revisited Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6795: 397-405. DOI: 10.1007/978-3-642-22321-1_34  0.395
2011 Charlier E, Domaratzki M, Harju T, Shallit J. Finite orbits of language operations Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6638: 204-215. DOI: 10.1007/978-3-642-21254-3-15  0.42
2009 Krieger D, Miller A, Rampersad N, Ravikumar B, Shallit J. Decimations of languages and state complexity Theoretical Computer Science. 410: 2401-2409. DOI: 10.1016/J.Tcs.2009.02.024  0.306
2009 Anderson T, Loftus J, Rampersad N, Santean N, Shallit J. Detecting palindromes, patterns and borders in regular languages Information and Computation. 207: 1096-1118. DOI: 10.1016/j.ic.2008.06.007  0.399
2009 Guay-Paquet M, Shallit J. Avoiding squares and overlaps over the natural numbers Discrete Mathematics. 309: 6245-6254. DOI: 10.1016/j.disc.2009.06.004  0.365
2009 Brzozowski J, Grant E, Shallit J. Closures in formal languages and Kuratowski's theorem Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5583: 125-144. DOI: 10.1007/978-3-642-02737-6_10  0.444
2008 Shallit J. A second course in formal languages and automata theory A Second Course in Formal Languages and Automata Theory. 1-240. DOI: 10.1017/CBO9780511808876  0.381
2008 Kao JY, Rampersad N, Shallit J, Silva M. Words avoiding repetitions in arithmetic progressions Theoretical Computer Science. 391: 126-137. DOI: 10.1016/j.tcs.2007.10.039  0.394
2008 Anderson T, Rampersad N, Santean N, Shallit J. Finite automata, palindromes, powers, and patterns Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5196: 52-63. DOI: 10.1007/978-3-540-88282-4_7  0.361
2006 Currie J, Rampersad N, Shallit J. Binary words containing infinitely many overlaps Electronic Journal of Combinatorics. 13: 1-10.  0.343
2005 Domaratzki M, Ellul K, Shallit J, Wang MW. Non-uniqueness and radius of cyclic unary NFAs International Journal of Foundations of Computer Science. 16: 883-896. DOI: 10.1142/S0129054105003352  0.49
2005 Krawetz B, Lawrence J, Shallit J. State complexity and the monoid of transformations of a finite set International Journal of Foundations of Computer Science. 16: 547-563. DOI: 10.1142/S0129054105003157  0.303
2005 Rampersad N, Shallit J, Wang MW. Avoiding large squares in infinite binary words Theoretical Computer Science. 339: 19-34. DOI: 10.1016/J.Tcs.2005.01.005  0.469
2005 Domaratzki M, Okhotin A, Shallit J. Enumeration of context-free languages and related structures 7th International Workshop On Descriptional Complexity of Formal Systems, Dcfs 2005 - Proceedings. 85-96.  0.419
2005 Lee J, Shallit J. Enumerating regular expressions and their languages Lecture Notes in Computer Science. 3317: 2-22.  0.329
2004 Karhumäki J, Shallit J. Polynomial versus exponential growth in repetition-free binary words Journal of Combinatorial Theory. Series A. 105: 335-347. DOI: 10.1016/J.Jcta.2003.12.004  0.347
2003 Pighizzini G, Shallit J, Wang MW. Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds Journal of Computer and System Sciences. 65: 393-414. DOI: 10.1006/Jcss.2002.1855  0.473
2002 Pighizzini G, Shallit J. Unary language operations, state complexity and jacobsthal's function International Journal of Foundations of Computer Science. 13: 145-159. DOI: 10.1142/S012905410200100X  0.306
2002 Shallit J, Wang Mw. On two-sided infinite fixed points of morphisms Theoretical Computer Science. 270: 659-675. DOI: 10.1016/S0304-3975(01)00092-5  0.408
1998 Glaister I, Shallit J. Automaticity III: Polynomial automaticity and context-free languages Computational Complexity. 7: 371-387.  0.446
1998 Allouche JP, Currie J, Shallit J. Extremal infinite overlap-free binary words Electronic Journal of Combinatorics. 5.  0.398
1998 Allouche JP, Shallit J. Generalized perturbed symmetry European Journal of Combinatorics. 19: 401-411.  0.349
1997 Pomerance C, Robson JM, Shallit J. Automaticity II: Descriptional complexity in the unary case Theoretical Computer Science. 180: 181-201. DOI: 10.1016/S0304-3975(96)00189-2  0.343
1996 Glaister I, Shallit J. A lower bound technique for the size of nondeterministic finite automata Information Processing Letters. 59: 75-77. DOI: 10.1016/0020-0190(96)00095-6  0.344
1996 Glaister I, Shallit J. Polynomial automaticity, context-free languages, and fixed points of morphisms (extended abstract) Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1113: 382-393.  0.462
1994 Enflo P, Granville A, Shallit J, Yu S. On sparse languages L such that LL = Σ Discrete Applied Mathematics. 52: 275-285. DOI: 10.1016/0166-218X(94)90146-5  0.415
1994 Shallit J. Numeration Systems, Linear Recurrences, and Regular Sets Information and Computation. 113: 331-347. DOI: 10.1006/inco.1994.1076  0.339
Show low-probability matches.