Publications

This page contains links to all of my publications, sorted by publication type. If you need one of my papers and you don’t have institutional access, contact me and I’ll be happy to send you a copy.

Note that publications in theoretical computer science customarily list authors alphabetically.

Peer-reviewed Journal Articles

  1. Arto Salomaa, Kai Salomaa, and Taylor J. Smith. Descriptional complexity of finite automata – selected highlights. Fundamenta Informaticae. To appear.
    arXiv:2301.03708
  2. Alastair May and Taylor J. Smith. Illustrating finite automata with Grail+ and TikZ. TUGboat: The Communications of the TEX Users Group. 45(1):97–101, 2024.
    arXiv:2404.03039
  3. Taylor J. Smith and Kai Salomaa. Recognition and complexity results for projection languages of two-dimensional automata. Journal of Automata, Languages, and Combinatorics, 28(1–3):201–220, 2023. Invited extended version of DCFS 2020 article.
  4. Taylor J. Smith and Kai Salomaa. Decision problems and projection languages for restricted variants of two-dimensional automata. Theoretical Computer Science, 870:153–164, May 2021. Invited extended version of CIAA 2019 article.
  5. 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.
  6. 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. Two-dimensional typewriter automata. In H. Bordihn, G. Horváth, and G. Vaszil, editors, Short Papers of the 12th Workshop on Non-Classical Models of Automata and Applications (NCMA 2022), pages 38–45, Debrecen, Hungary. Faculty of Informatics, University of Debrecen, Aug. 2022.
    arXiv:2207.10016
  2. Taylor J. Smith and Kai Salomaa. Degrees of restriction for two-dimensional automata. In S. Maneth, editor, Proceedings of the 25th International Conference on Implementation and Application of Automata (CIAA 2021), volume 12803 of Lecture Notes in Computer Science, pages 77–89, Bremen, Germany. Springer, Jul. 2021.
    arXiv:2105.01179
  3. 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
  4. 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
  5. 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
  6. 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. Closure, decidability, and complexity results for restricted variants of two-dimensional automata. Doctoral thesis, Queen’s University, 2021. xi+147pp.
  2. Taylor J. Smith. Properties of two-dimensional words. Master’s thesis, University of Waterloo, 2017. vii+58pp.
  3. 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. Pantelis Andreou, Stavros Konstantinidis, and Taylor J. Smith. Improved randomized approximation of hard universality and emptiness problems, Mar. 2024. arXiv:2403.08707.

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.