Tim Smith E-mail: timsmith3@gmail.com

About Me

I am currently employed as a software engineer in the Seattle area. See below for my academic background and links to my published research. I also have a portfolio of various projects I have undertaken. Inquiries are welcome.

My research has explored infinite words (symbolic sequences) and their relationships with formal languages and automata. More broadly, I am interested in formal languages, automata, and theoretical computer science generally, as well as other topics including prediction/classification, ranking/rating systems, game/decision theory, and automated proof checking.

From 2016 to 2017, I was a postdoctoral researcher in the School of Computer Science at the University of Waterloo. My supervisor was Jeffrey Shallit.

From 2015 to 2016, I was a postdoctoral researcher in the Laboratoire d'Informatique Gaspard-Monge at Université Paris-Est Marne-la-Vallée. My supervisor was Dominique Perrin.

I received my Ph.D. in Computer Science from Northeastern University in May 2015. My advisor was Rajmohan Rajaraman. I received my MSc in Computer Science from The University of Auckland and my B.S. in Computer Science from Clemson University.

Journal Publications

• A Characterization of Morphic Words with Polynomial Growth
  Tim Smith.
  DMTCS - Volume 22, Number 1, February 2020.
  [PDF] [BibTeX] [DOI]

• Additive Number Theory via Automata Theory
  Aayush Rajasekaran, Jeffrey Shallit, and Tim Smith.
  Theory of Computing Systems - May 2019.
  [PDF] [BibTeX] [DOI]

• A New Pumping Lemma for Indexed Languages, with an Application to Infinite Words
  Tim Smith.
  Information and Computation - Volume 252, February 2017, pages 176–186.
  [PDF] [BibTeX] [DOI]

• Prediction of Infinite Words with Automata
  Tim Smith.
  Theory of Computing Systems - December 2016.
  [PDF] [BibTeX] [DOI]

• On Infinite Words Determined by L Systems
  Tim Smith.
  Theoretical Computer Science - Volume 595, August 2015, pages 1–10.
  [PDF] [BibTeX] [DOI]

Conference Publications

• Sums of Palindromes: an Approach via Automata
  Aayush Rajasekaran, Jeffrey Shallit, and Tim Smith.
  STACS 2018 - 35th International Symposium on Theoretical Aspects of Computer Science, Caen, France, February–March 2018.
  [PDF] [BibTeX] [DOI]

• Undecidability and Finite Automata
  Jörg Endrullis, Jeffrey Shallit, and Tim Smith.
  DLT 2017 - 21st International Conference on Developments in Language Theory, Liège, Belgium, August 2017.
  [PDF] [BibTeX] [DOI]

• Prediction of Infinite Words with Automata
  Tim Smith.
  CSR 2016 - 11th International Computer Science Symposium in Russia, St. Petersburg, Russia, June 2016.
  [PDF] [BibTeX] [DOI]

• On Infinite Words Determined by Indexed Languages
  Tim Smith.
  MFCS 2014 - 39th International Symposium on Mathematical Foundations of Computer Science, Budapest, Hungary, August 2014.
  [PDF] [BibTeX] [DOI]

• A Pumping Lemma for Two-Way Finite Transducers
  Tim Smith.
  MFCS 2014 - 39th International Symposium on Mathematical Foundations of Computer Science, Budapest, Hungary, August 2014.
  [PDF] [BibTeX] [DOI] [Notes and Errata]

• On Infinite Words Determined by Stack Automata
  Tim Smith.
  FSTTCS 2013 - 33rd International Conference on Foundations of Software Technology and Theoretical Computer Science, Guwahati, India, December 2013.
  [PDF] [BibTeX] [DOI]

• On Infinite Words Determined by L Systems
  Tim Smith.
  WORDS 2013 - 9th International Conference on Words, Turku, Finland, September 2013.
  [PDF] [BibTeX] [DOI]

• Infiniteness and Boundedness in 0L, DT0L, and T0L Systems
  Tim Smith.
  LATA 2013 - 7th International Conference on Language and Automata Theory and Applications, Bilbao, Spain, April 2013.
  [PDF] [BibTeX] [DOI] [Errata]

Instructor

• 16F - CS 341 - Algorithms [Waterloo]
• 13S - CS 1800 - Discrete Structures [Northeastern]

Teaching Assistant

• 12F - CS 2500 - Fundamentals of Computer Science 1
  
• 12S - CS 2500 - Fundamentals of Computer Science 1
  
• 11F - CS 2500 - Fundamentals of Computer Science 1
  
• 11S - CS 2800 - Logic and Computation
• 10F - CS 2500 - Fundamentals of Computer Science 1
  

Student

• 11F - CS 7400 - Intensive Principles of Programming Languages
  
• 11S - CS 7600 - Intensive Computer Systems
  
• 10F - CS 6140 - Machine Learning
  
• 10F - CS 7480 - Computational Logic