4 papers
Almost free algebras: from the word problem to elimination of quantifiers
Yifan Jia, Heer Tern Koh, Bakh Khoussainov
Term algebras are important objects in computer science and are correspondingly well-studied. A natural generalization is to quotient these algebras by finitely many ground term eq…
Automatic constraint satisfaction problem
Andrei Bulatov, Xiaoyang Gong, Bakh Khoussainov +1
We study constraint satisfaction problems (CSPs) where the constraint languages are defined by finite automata, giving rise to automata-based CSPs. The key notion is the concept of…
Large Scale Geometries of Infinite Strings
Bakhadyr Khoussainov, Toru Takisaka
We introduce geometric consideration into the theory of formal languages. We aim to shed light on our understanding of global patterns that occur on infinite strings. We utilise me…
Facility Location Games Beyond Single-Peakedness: the Entrance Fee Model
Mengfan Ma, Mingyu Xiao, Tian Bai +1
The facility location game has been studied extensively in mechanism design. In the classical model, each agent's cost is solely determined by her distance to the nearest facility.…