Search Results

Documents authored by Gao, Younan

Document
DOI: 10.4230/LIPIcs.OPODIS.2024.11
Gathering Teams of Deterministic Finite Automata on a Line

Authors: Younan Gao and Andrzej Pelc

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
Several mobile agents, modelled as deterministic finite automata, navigate in an infinite line in synchronous rounds. All agents start in the same round. In each round, an agent can move to one of the two neighboring nodes, or stay idle. Agents have distinct labels which are integers from the set {1,…,L}. They start in teams, each of which consists of x agents, for some fixed integer x. Agents in a team have the same starting node. The adversary decides the compositions of teams, and their starting nodes. Whenever an agent enters a node, it sees the entry port number and the states of all collocated agents; this information forms the input of the agent on the basis of which it transits to the next state and decides the current action. The aim is for all agents to gather at the same node and stop. Gathering is feasible, if this task can be accomplished for any decisions of the adversary, and its time is the worst-case number of rounds from the start till gathering. We consider the feasibility and time complexity of gathering teams of agents, and give a complete solution of this problem. It turns out that both feasibility and complexity of gathering depend on the crucial parameter x which is the size of teams. For the oriented line, gathering is impossible if x = 1, and it can be accomplished in time O(D), for x > 1, where D is the distance between the starting nodes of the most distant teams. This complexity is of course optimal. For the unoriented line, the situation is different. For x = 1, gathering is also impossible, but for x = 2, the optimal time of gathering is Θ(Dlog L), and for x ≥ 3 the optimal time of gathering is Θ(D). Solving the gathering problem for agents that are finite automata navigating in an infinite environment requires new methodological tools. Traditional gathering techniques in graphs are count driven: agents make decisions based on counting steps. Since distances between agents may be unbounded, agents have to count unbounded numbers of steps. When agents are finite automata, counting unbounded numbers of steps is impossible, hence we must use different methods. In all our gathering algorithms, changes of the agents' behavior are triggered not by counting steps but by events which are meetings between agents during which they interact. Hence our new technique is event driven. Designing the behavior of the agents based on meeting events, so as to guarantee gathering regardless of the adversary’s decisions is our main methodological contribution.
Cite as

Younan Gao and Andrzej Pelc. Gathering Teams of Deterministic Finite Automata on a Line. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.OPODIS.2024.11,
  author =	{Gao, Younan and Pelc, Andrzej},
  title =	{{Gathering Teams of Deterministic Finite Automata on a Line}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.11},
  URN =		{urn:nbn:de:0030-drops-225478},
  doi =		{10.4230/LIPIcs.OPODIS.2024.11},
  annote =	{Keywords: Gathering, deterministic finite automaton, mobile agent, team of agents, line, time}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.59
Faster Path Queries in Colored Trees via Sparse Matrix Multiplication and Min-Plus Product

Authors: Younan Gao and Meng He

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Let T be an ordinal tree on n nodes in which each node is assigned a color. We consider the batched colored path counting problem and the batched path mode/least frequent element query problem, in which given n query paths, each identified by a pair of nodes in T, one is asked to answer queries of the following forms: How many distinct colors are there on each query path (i.e. the colored path counting problem); what is the color on each query path that occurs at least/most as frequently as any other colors (i.e. the path mode/least frequent element query problem). By reducing the batched colored path counting problem to sparse matrix multiplication, we design a solution that answers n colored path counting queries in Õ(n^{2ω/(ω+1)}) = O(n^1.40704) time in total, while we reduce batched path mode/least frequent element query to the min-plus-query-witness problem so that we can answer a batch of n queries in Õ(n^{{24+2ω}/{17+ω}}) = O(n^1.483814) time. Previously, both problems could only be solved in Õ(n^1.5) time. Based on similar techniques, we design a dynamic colored path counting structure supporting both queries and updates in Õ(n^{{ω+1}/{ω+3}}) = O(n^0.627759) time, while our dynamic path mode/least frequent element query structures support each operation in Õ(n^{{16+ω(1,2,1)}/{26+ω(1,2,1)}}) = O(n^0.658139) time, where ω(1, 2, 1) denotes the minimum value such that the product of an n × n² matrix and an n² × n matrix can be computed in O(n^{ω(1, 2, 1)+ε}) time for any constant ε > 0. We also solve batched range mode/least frequent element query problems over arrays in Õ(n^{{18+2ω}/{13+ω}}) = O(n^1.479603) time. Both problems can be viewed as special cases of these batched path queries, and previously, the fastest algorithm for batched range mode queries and batched range least frequent element queries use O(n^1.4805) and Õ(n^1.5) time, respectively.
Cite as

Younan Gao and Meng He. Faster Path Queries in Colored Trees via Sparse Matrix Multiplication and Min-Plus Product. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.ESA.2022.59,
  author =	{Gao, Younan and He, Meng},
  title =	{{Faster Path Queries in Colored Trees via Sparse Matrix Multiplication and Min-Plus Product}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{59:1--59:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.59},
  URN =		{urn:nbn:de:0030-drops-169971},
  doi =		{10.4230/LIPIcs.ESA.2022.59},
  annote =	{Keywords: min-plus product, range mode queries, range least frequent queries, path queries, colored path counting, path mode queries, path least frequent queries}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.46
Space Efficient Two-Dimensional Orthogonal Colored Range Counting

Authors: Younan Gao and Meng He

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
In the two-dimensional orthogonal colored range counting problem, we preprocess a set, P, of n colored points on the plane, such that given an orthogonal query rectangle, the number of distinct colors of the points contained in this rectangle can be computed efficiently. For this problem, we design three new solutions, and the bounds of each can be expressed in some form of time-space tradeoff. By setting appropriate parameter values for these solutions, we can achieve new specific results with (the space costs are in words and ε is an arbitrary constant in (0,1)): - O(nlg³ n) space and O(√nlg^{5/2} n lg lg n) query time; - O(nlg² n) space and O(√nlg^{4+ε} n) query time; - O(n (lg² n)/(lg lg n)) space and O(√nlg^{5+ε} n) query time; - O(nlg n) space and O(n^{1/2+ε}) query time. A known conditional lower bound to this problem based on Boolean matrix multiplication gives some evidence on the difficulty of achieving near-linear space solutions with query time better than √n by more than a polylogarithmic factor using purely combinatorial approaches. Thus the time and space bounds in all these results are efficient. Previously, among solutions with similar query times, the most space-efficient solution uses O(nlg⁴ n) space to answer queries in O(√nlg⁸ n) time (SIAM. J. Comp. 2008). Thus the new results listed above all achieve improvements in space efficiency, while all but the last result achieve speed-up in query time as well.
Cite as

Younan Gao and Meng He. Space Efficient Two-Dimensional Orthogonal Colored Range Counting. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 46:1-46:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.ESA.2021.46,
  author =	{Gao, Younan and He, Meng},
  title =	{{Space Efficient Two-Dimensional Orthogonal Colored Range Counting}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{46:1--46:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.46},
  URN =		{urn:nbn:de:0030-drops-146277},
  doi =		{10.4230/LIPIcs.ESA.2021.46},
  annote =	{Keywords: 2D Colored orthogonal range counting, stabbing queries, geometric data structures}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.54
Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing

Authors: Younan Gao, Meng He, and Yakov Nekrich

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Under the word RAM model, we design three data structures that can be constructed in O(n √{lg n}) time over n points in an n × n grid. The first data structure is an O(n lg^ε n)-word structure supporting orthogonal range reporting in O(lg lg n+k) time, where k denotes output size and ε is an arbitrarily small constant. The second is an O(n lg lg n)-word structure supporting orthogonal range successor in O(lg lg n) time, while the third is an O(n lg^ε n)-word structure supporting sorted range reporting in O(lg lg n+k) time. The query times of these data structures are optimal when the space costs must be within O(n polylog n) words. Their exact space bounds match those of the best known results achieving the same query times, and the O(n √{lg n}) construction time beats the previous bounds on preprocessing. Previously, among 2d range search structures, only the orthogonal range counting structure of Chan and Pǎtraşcu (SODA 2010) and the linear space, O(lg^ε n) query time structure for orthogonal range successor by Belazzougui and Puglisi (SODA 2016) can be built in the same O(n √{lg n}) time. Hence our work is the first that achieve the same preprocessing time for optimal orthogonal range reporting and range successor. We also apply our results to improve the construction time of text indexes.
Cite as

Younan Gao, Meng He, and Yakov Nekrich. Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 54:1-54:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.ESA.2020.54,
  author =	{Gao, Younan and He, Meng and Nekrich, Yakov},
  title =	{{Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{54:1--54:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.54},
  URN =		{urn:nbn:de:0030-drops-129202},
  doi =		{10.4230/LIPIcs.ESA.2020.54},
  annote =	{Keywords: orthogonal range search, geometric data structures, orthogonal range reporting, orthogonal range successor, sorted range reporting, text indexing, word RAM}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact