Taylor J. Smith

Publications

Publications in theoretical computer science customarily list authors alphabetically.

Peer-reviewed Journal Articles

  1. Taylor J. Smith and Kai Salomaa. Decision problems and projection languages for restricted variants of two-dimensional automata. Theoretical Computer Science. To appear. Invited extended version of CIAA 2019 article.
  2. Da-Jung Cho, Yo-Sub Han, Kai Salomaa, and Taylor J. Smith. Site-directed insertion: Language equations and decision problems. Theoretical Computer Science, 798:40–51, Dec. 2019. Invited extended version of DCFS 2018 article.
  3. Guilhem Gamard, Gwenaël Richomme, Jeffrey Shallit, and Taylor J. Smith. Periodicity in rectangular arrays. Information Processing Letters, 118:58–63, Feb. 2017.
    arXiv:1602.06915

Peer-reviewed Conference Articles

  1. Taylor J. Smith and Kai Salomaa. Concatenation operations and restricted variants of two-dimensional automata. In T. Bureš et al., editors, Proceedings of the 47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2021), volume 12607 of Lecture Notes in Computer Science, pages 147–158, Bolzano-Bozen, Italy. Springer, Jan. 2021.
    arXiv:2008.11164
  2. Taylor J. Smith and Kai Salomaa. Recognition and complexity results for projection languages of two-dimensional automata. In G. Jirásková and G. Pighizzini, editors, Proceedings of the 22nd International Conference on Descriptional Complexity of Formal Systems (DCFS 2020), volume 12442 of Lecture Notes in Computer Science, pages 206–218, Vienna, Austria. Springer, Aug. 2020.
    arXiv:2009.00602
  3. Taylor J. Smith and Kai Salomaa. Decision problems for restricted variants of two-dimensional automata. In M. Hospodár and G. Jirásková, editors, Proceedings of the 24th International Conference on Implementation and Application of Automata (CIAA 2019), volume 11601 of Lecture Notes in Computer Science, pages 222–234, Košice, Slovakia. Springer, Jul. 2019.
    Sheng Yu Award for Best Paper
    arXiv:1904.11100
  4. Da-Jung Cho, Yo-Sub Han, Kai Salomaa, and Taylor J. Smith. Site-directed insertion: Decision problems, maximality and minimality. In S. Konstantinidis and G. Pighizzini, editors, Proceedings of the 20th International Conference on Descriptional Complexity of Formal Systems (DCFS 2018), volume 10952 of Lecture Notes in Computer Science, pages 49–61, Halifax, Canada. Springer, Jul. 2018.
    arXiv:1804.11017

Technical Reports

  1. Taylor J. Smith. Two-dimensional automata. Technical report 2019-637, School of Computing, Queen’s University, Kingston, Canada, Jan. 2019. 27pp.

Theses

  1. Taylor J. Smith. Properties of two-dimensional words. Master’s thesis, University of Waterloo, 2017. vii+58pp.
  2. Taylor J. Smith. A study of solid hypercodes. Bachelor’s thesis, University of Western Ontario, 2015. v+30pp.
    Szilard Award in Theoretical Computer Science

Submitted Works

  1. Taylor J. Smith and Kai Salomaa. Degrees of restriction for two-dimensional automata, May 2021. arXiv:2105.01179. To appear in Proceedings of the 25th International Conference on Implementation and Application of Automata (CIAA 2021).

Unpublished Works

The following works have not appeared anywhere, but I list them here for completeness.

  1. Taylor J. Smith. Computational complexity of decision problems for finite automata. Nov. 2017. 8pp.
  2. Taylor J. Smith. A tour of the Chomsky hierarchy with applications to pattern recognition. Nov. 2017. 6pp.
  3. Zachary Frenette, William Herring, and Taylor J. Smith. Secret sharing schemes for threshold graphs. Aug. 2016. 10pp.
  4. Sajed Haque and Taylor J. Smith. On a variation of the Lovász local lemma. Apr. 2016. 8pp.
  5. Taylor J. Smith. The relationship between formal languages and natural languages. Apr. 2016. 6pp.