Zobrazeno 1 - 10
of 171
pro vyhledávání: '"Khoussainov, Bakhadyr"'
Publikováno v:
Theoretical Computer Science, 947 (2023) 113705
We construct a FA-presentation $\psi: L \rightarrow \mathbb{N}$ of the structure $(\mathbb{N};\mathrm{S})$ for which a numerical characteristic $r(n)$ defined as the maximum number $\psi(w)$ for all strings $w \in L$ of length less than or equal to $
Externí odkaz:
http://arxiv.org/abs/2302.01009
Listing dense subgraphs in large graphs plays a key task in varieties of network analysis applications like community detection. Clique, as the densest model, has been widely investigated. However, in practice, communities rarely form as cliques for
Externí odkaz:
http://arxiv.org/abs/2202.08737
Quasi-isometries are mappings on graphs, with distance-distortions parameterized by a multiplicative factor and an additive constant. The distance-distortions of quasi-isometries are in a general form that captures a wide range of distance-approximat
Externí odkaz:
http://arxiv.org/abs/2111.13238
Publikováno v:
In Computers and Operations Research September 2024 169
Autor:
Khoussainov, Bakhadyr, Takisaka, Toru
Publikováno v:
32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017
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 methods of geometric group theory. Our emphasis is on large scale geomet
Externí odkaz:
http://arxiv.org/abs/1908.03800
Autor:
Gao, Ziyuan, Jain, Sanjay, Khoussainov, Bakhadyr, Li, Wei, Melnikov, Alexander, Seidel, Karen, Stephan, Frank
This paper introduces and studies a notion of \emph{algorithmic randomness} for subgroups of rationals. Given a randomly generated additive subgroup $(G,+)$ of rationals, two main questions are addressed: first, what are the model-theoretic and recur
Externí odkaz:
http://arxiv.org/abs/1901.04743
This paper studies tree-automatic ordinals (or equivalently, well-founded linearly ordered sets) together with the ordinal addition operation +. Informally, these are ordinals such that their elements are coded by finite trees for which the linear or
Externí odkaz:
http://arxiv.org/abs/1810.13153
Publikováno v:
Berdinsky D., Khoussainov B., "Cayley automatic representations of wreath products", International Journal of Foundations of Computer Science, V. 27, N 2, pp. 147-159 (2016)
We construct the representations of Cayley graphs of wreath products using finite automata, pushdown automata and nested stack automata. These representations are in accordance with the notion of Cayley automatic groups introduced by Kharlampovich, K
Externí odkaz:
http://arxiv.org/abs/1511.01630
Publikováno v:
Theoretical Computer Science, Volume 562, 11 January 2015, Pages 227-242
We investigate dynamic algorithms for the interval scheduling problem. Our algorithm runs in amortised time $O(\log n)$ for query operation and $O(d\log^2 n)$ for insertion and removal operations, where $n$ and $d$ are the maximal numbers of interval
Externí odkaz:
http://arxiv.org/abs/1412.8005
In this paper we introduce the concept of a Cayley graph automatic group (CGA group or graph automatic group, for short) which generalizes the standard notion of an automatic group. Like the usual automatic groups graph automatic ones enjoy many nice
Externí odkaz:
http://arxiv.org/abs/1107.3645