Browsing Faculty of Design and Creative Technologies (Te Ara Auaha) by Author "Khoussainov, B"

Now showing items 1-8 of 8

    • A dynamic algorithm for reachability games on trees

      Khoussainov, B; Liu, J; Khaliq, I (Springer, 2009)
      Our goal is to start the investigation of dynamic algorithms for solving games that are played on finite graphs. The dynamic game determinacy problem calls for finding efficient algorithms that decide the winner of the ...

    • A dynamic algorithm for reachability games on trees

      Khoussainov, B; Liu, J; Khaliq, I (Springer Berlin / Heidelberg, 2009)
      Our goal is to start the investigation of dynamic algorithms for solving games that are played on finite graphs. The dynamic game determinacy problem calls for finding efficient algorithms that decide the winner of the ...

    • Computable categoricity of graphs with finite components

      Csima, B; Khoussainov, B; Liu, J (Springer Berlin / Heidelberg, 2008)
      A computable graph is computably categorical if any two computable presentations of the graph are computably isomorphic. In this paper we investigate the class of computably categorical graphs. We restrict ourselves to ...

    • Extracting winning strategies in update games

      Liu, J; Khaliq, I; Khoussainov, B (Springer Berlin / Heidelberg, 2011)
      This paper investigates algorithms for extracting winning strategies in two-player games played on nite graphs. We focus on a special class of games called update games. We present a procedure for extracting winning ...

    • On complexity of Ehrenfeucht-Fraïssé games

      Khoussainov, B; Liu, J (Springer Berlin / Heidelberg, 2007)
      In this paper we initiate the study of Ehrenfeucht-Fraïssé games for some standard finite structures. Examples of such standard structures are equivalence relations, trees, unary relation structures, Boolean algebras, and ...

    • Solving infinite games on trees with back-edges

      Liu, J; Khoussainov, B; Gandhi, A (Australian Computer Society (ACS), 2012)
      We study the computational complexity of solving the following problem: Given a game G played on a fi- nite directed graph G, output all nodes in G from which a specific player wins the game G. We pro- vide algorithms for ...

    • Unary automatic graphs: an algorithmic approach

      Khoussainov, B; Liu, J; Minnes, M (Cambridge University Press, 2009)
      This paper studies infinite graphs produced from a natural unfolding operation applied to finite graphs. Graphs produced using such operations are of finite degree and automatic over the unary alphabet (that is, they can ...

    • Unary automatic graphs: an algorithmic perspective

      Khoussainov, B; Liu, J; Minnes, M (Springer-Verlag Berlin, Heidelberg, 2008)
      This paper studies infinite graphs produced from a natural unfolding operation applied to finite graphs. Graphs produced via such operations are of finite degree and can be described by finite automata over the unary alphabet. ...