Search

(Non)-Deterministic finite automata are one of the simplest models of computation studied in automata theory. Here we study them through the lens of succinct data structures. Towards this goal, we design a data structure for any deterministic automaton D having n states over a σ -letter alphabet Σ using (σ − 1) n log ⁡ n (1 + o (1)) bits, that determines, given a string x , whether D accepts x in optimal O (| x |) time. We also consider the case when there are N < σ n non-failure transitions, and obtain various time-space trade-offs. Here some of our results are better than the recent work of Cotumaccio and Prezza (SODA 2021). We also exhibit a data structure for non-deterministic automaton N using σ n 2 + n bits that takes O (n 2 | x |) time for string membership checking. Finally, we also provide time and space efficient algorithms for performing several standard operations on the languages accepted by finite automata. [ABSTRACT FROM AUTHOR]

A tournament is an orientation of a complete graph. It is well-known that any tournament has a vertex from which every other vertex can be reached by a path of length at most 2. Such a vertex is called a king or a 2 -king. It is also known that to find such a vertex, Ω n 4 / 3 queries (to the adjacency matrix) are necessary and O n 3 / 2 probes are sufficient. It is a long standing open problem to narrow this gap between the upper and lower bound. We first show that – the adversary Ajtai et al. (2016) and Shen et al. (2003) used to prove the known Ω n 4 / 3 lower bound cannot be used to prove a better lower bound, by giving an algorithm that achieves the bound against the same adversary; Clearly in any tournament there is a vertex from which every other vertex is reachable by a path of length at most d for any d ≥ 2 and such a vertex is called a d -king. The bounds for finding a 2 -king have been generalized (Ajtai et al., 2016) to obtain generalized upper and lower bounds to find a d -king. We show that – our algorithm against the weak adversary works against such an adversary for finding d -kings too. More generally, if we can find a 2 -king in O n 4 / 3 time, then we can find a d -king in asymptotically optimal time for any d ≥ 2. This was conjectured in an earlier paper. Then we address the complexity of finding a set of d -kings, i.e. a small subset of vertices such that every vertex is reachable from one of them by a path of length at most d. Such a set is called a d -cover. – We generalize the lower bound for finding a d -king to give a lower bound for finding k sized d -covers. We complement it with an algorithm matching this bound for k ∈ Ω (lg n). For d = 1 for example, our results imply that we can find a (lg n − lg lg n + k) -sized dominating set in O n 2 / k time and that this bound is optimal. Finally we develop a dynamic data structure so that whenever a new vertex is added to the tournament, we can find a king of the new tournament in O (n) time. [ABSTRACT FROM AUTHOR]

We consider the problem of designing succinct navigational oracles, i.e., succinct data structures supporting basic navigational queries such as degree, adjacency and neighborhood efficiently for intersection graphs on a circle, which include graph classes such as circle graphs , k-polygon-circle graphs , circle-trapezoid graphs , trapezoid graphs. The degree query reports the number of incident edges to a given vertex, the adjacency query asks if there is an edge between two given vertices, and the neighborhood query enumerates all the neighbors of a given vertex. We first prove a general lower bound for these intersection graph classes, and then present a uniform approach that lets us obtain matching lower and upper bounds for representing each of these graph classes. More specifically, our lower bound proofs use a unified technique to produce tight bounds for all these classes, and this is followed by our data structures which are also obtained from a unified representation method to achieve succinctness for each class. In addition, we prove a lower bound of space for representing trapezoid graphs, and give a succinct navigational oracle for this class of graphs. [ABSTRACT FROM AUTHOR]

Read-only memory (ROM) model is a classical model of computation to study time-space tradeoffs of algorithms. More recently, several graph algorithms have been studied under ROM model. In this paper, we study graph algorithms under two different relaxations of ROM model, referred to as the implicit and rotate models, and show that these simple relaxations allow us to implement fundamental graph search methods like BFS and DFS more space efficiently than in ROM model. All our algorithms are simple but quite subtle, and we believe that these models are practical enough to spur interest for other graph problems in these models. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a model for studying energy efficient algorithms by extending the well-studied comparison model. In our model, the result of a comparison is determined based on two parameters: (i) the energy used to perform a comparison, and (ii) the absolute difference between the two values being compared – thus introducing an energy-accuracy trade-off. This model also extends the ideas presented by Geissmann and Penna [SOFSEM 2018] and Funke et al. [Comput. Geom. 2005] wherein they use two distinct types of comparisons namely low and full-energy (cheap and expensive) comparisons, by introducing multiple types of comparisons. In this extension, the accuracy of a comparison becomes a function of the energy used. We consider the fundamental problems of (i) sorting (ii) selection (iii) searching, and design efficient algorithms for these problems in the new model. We also present lower bounds on the energy usage for some of these problems, showing that some of our algorithms are asymptotically optimal with respect to the energy usage. [ABSTRACT FROM AUTHOR]