{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T06:35:54Z","timestamp":1780382154685,"version":"3.54.1"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,3,13]],"date-time":"2019-03-13T00:00:00Z","timestamp":1552435200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2019,3,13]]},"abstract":"<jats:p>With increased public interest in the ancient game of Go since 2016, it is an espe- cially good time to use it in teaching. The game is an excellent source of exercises in the theory of computation. We give some exercises developed during our research on Go which were then used when teaching this subject at Monash University. These are based on One-Dimensional Go (1D-Go) which uses a path graph as its board. They are about determining whether or not a position is legal and counting the number of legal positions. Curriculum elements that may be illustrated and practised using 1D-Go include: regular expressions, linear recurrences, proof by induction, nite automata, regular grammars, context-free grammars and languages, pushdown automata, and Turing machines.<\/jats:p>","DOI":"10.1145\/3319627.3319639","type":"journal-article","created":{"date-parts":[[2019,3,14]],"date-time":"2019-03-14T17:11:58Z","timestamp":1552583518000},"page":"65-78","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Using Go in teaching the theory of computation"],"prefix":"10.1145","volume":"50","author":[{"given":"Graham","family":"Farr","sequence":"first","affiliation":[{"name":"Monash University, Clayton, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,3,13]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"BadukTV http:\/\/www.tvbaduk.com\/  BadukTV http:\/\/www.tvbaduk.com\/"},{"key":"e_1_2_1_2_1","volume-title":"London","author":"Fairbairn J.","year":"1995"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00831-9"},{"key":"e_1_2_1_4_1","first-page":"1148","volume":"54","author":"Farr G. E.","year":"2017","journal-title":"J. Korean Math. Soc."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.08.018"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1038\/529446a"},{"key":"e_1_2_1_7_1","unstructured":"International Go Federation About the IGF 14 June 2010 http:\/\/intergofed.org\/ about-the-igf.html  International Go Federation About the IGF 14 June 2010 http:\/\/intergofed.org\/ about-the-igf.html"},{"key":"e_1_2_1_8_1","unstructured":"K. Iwamoto Go for Beginners Ishi Press 1972 and Penguin Books 1976.  K. Iwamoto Go for Beginners Ishi Press 1972 and Penguin Books 1976."},{"key":"e_1_2_1_9_1","volume-title":"Motherboard","author":"L. Johnson After","year":"2016"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"C. Koch How the computer beat the Go master Scienti c American 19 March 2016 https:\/\/www.scientificamerican.com\/article\/how-the-computer- beat-the-go-master\/  C. Koch How the computer beat the Go master Scienti c American 19 March 2016 https:\/\/www.scientificamerican.com\/article\/how-the-computer- beat-the-go-master\/","DOI":"10.1038\/scientificamericanmind0716-20"},{"key":"e_1_2_1_11_1","volume-title":"Wired","author":"Metz C.","year":"2017"},{"key":"e_1_2_1_12_1","unstructured":"G.-C. Pascutto leela-zero https:\/\/github.com\/gcp\/leela-zero 10 May 2018.  G.-C. Pascutto leela-zero https:\/\/github.com\/gcp\/leela-zero 10 May 2018."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCIAIG.2010.2098876"},{"key":"e_1_2_1_14_1","unstructured":"S. Shead There is a worldwide shortage of the board game Go after Google DeepMind showcased it to 280 million people 4 April 2016 https:\/\/www.businessinsider.com.au\/go-board-game-in-demand-after- google-deepmind-put-it-in-the-spotlight-2016--4  S. Shead There is a worldwide shortage of the board game Go after Google DeepMind showcased it to 280 million people 4 April 2016 https:\/\/www.businessinsider.com.au\/go-board-game-in-demand-after- google-deepmind-put-it-in-the-spotlight-2016--4"},{"key":"e_1_2_1_15_1","first-page":"489","volume":"529","author":"David Silver","year":"2016","journal-title":"Nature"},{"key":"e_1_2_1_16_1","unstructured":"Y. Tian and L. Zitnick Facebook open sources ELF OpenGo https:\/\/research.fb. com\/facebook-open-sources-elf-opengo\/ 2 May 2018.  Y. Tian and L. Zitnick Facebook open sources ELF OpenGo https:\/\/research.fb. com\/facebook-open-sources-elf-opengo\/ 2 May 2018."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"J. Tromp Number of legal Go positions https:\/\/tromp.github.io\/go\/legal.html Jan. 2016.  J. Tromp Number of legal Go positions https:\/\/tromp.github.io\/go\/legal.html Jan. 2016.","DOI":"10.1007\/978-3-319-50935-8_17"},{"key":"e_1_2_1_18_1","series-title":"Lecture Notes in Computer Science 10068","first-page":"190","volume-title":"A. Plaat, W. Kosters and J. van den Herik (eds.), Computers and Games: 9th International Conference, CG 2016 (Leiden, The Netherlands, 29 June {","author":"Tromp J.","year":"2016"},{"key":"e_1_2_1_19_1","first-page":"99","volume-title":"Computers and Games: 5th International Conference, CG 2006 (Turin, 29{31","author":"Tromp J.","year":"2006"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3319627.3319639","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3319627.3319639","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:05Z","timestamp":1750208885000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3319627.3319639"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,13]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,3,13]]}},"alternative-id":["10.1145\/3319627.3319639"],"URL":"https:\/\/doi.org\/10.1145\/3319627.3319639","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2019,3,13]]},"assertion":[{"value":"2019-03-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}