Tomasz Jurdziński

I&C Journal 2023 Journal Article

Deterministic size discovery and topology recognition in radio networks with short labels

• Adam Gańczorz
• Tomasz Jurdziński
• Mateusz Lewko
• Andrzej Pelc

We consider size discovery and topology recognition in radio networks without collision detection, modeled by simple undirected connected graphs. The aim of size discovery is that all nodes output the number of nodes in the graph, and in the task of topology recognition, each node has to learn the topology of the graph and its position in it. Nodes are assigned labels which are (not necessarily different) binary strings. Each node uses its own label as input when executing the algorithm. The length of a labeling scheme is the largest length of a label. Our goal is to construct short labeling schemes for size discovery and topology recognition in arbitrary radio networks, and to design efficient deterministic distributed algorithms for each of these tasks, using these short schemes. In both cases, the length of our labeling schemes is asymptotically optimal.

TCS Journal 2023 Journal Article

Guest editorial: Structural Information and Communication Complexity 2021

• Klaus-Tycho Foerster
• Tomasz Jurdziński
• Stefan Schmid

TCS Journal 2019 Journal Article

Online packet scheduling under adversarial errors

• Paweł Garncarek
• Tomasz Jurdziński
• Dariusz R. Kowalski
• Krzysztof Loryś

We consider the problem of scheduling packets of different sizes via a directed communication link prone to errors, where dynamic packet arrivals and errors are modeled by an adversary. Packets arrive over time to be transmitted over a channel in which instantaneous errors occur at times not known to the algorithm in advance. We focus on estimating the competitive throughput of online scheduling algorithms defined as the ratio between the total size of packets successfully transmitted by an online algorithm and the largest total size of packets which can be transmitted for the same arrival and error patterns. First, we design two online algorithms with optimal competitive throughput in various scenarios. One algorithm works for any f ≥ 1 channels and attains the competitive throughput 1/2 provided that sizes of packets satisfy the divisibility property (i. e. , any larger size is divisible by any smaller). The other algorithm achieves the optimal competitive throughput in ( 1 / 3, 1 / 2 ] for arbitrary sizes of packets on one communication channel, where the exact value of the competitive throughput depends on the sizes of packets. Second, we focus on algorithms working with speedup s ≥ 1. In this setting, online algorithms transmit packets s times faster than the offline optimum solution they are compared against. We design an algorithm which attains the competitive throughput 1 if it works with speedup 2 in the case that sizes of packets satisfy the divisibility property and with speedup s ∈ [ 4, 6 ) for arbitrary sizes of packets. This demonstrates that throughput of the best online fault-tolerant scheduling algorithms scales well with resource augmentation.

I&C Journal 2007 Journal Article

Lower bound technique for length-reducing automata

• Tomasz Jurdziński
• Krzysztof Loryś

The class of growing context-sensitive languages (GCSL) was proposed as a naturally defined subclass of context-sensitive languages whose membership problem is solvable in polynomial time. Growing context-sensitive languages and their deterministic counterpart called Church–Rosser languages (CRL) complement the Chomsky hierarchy in a natural way, as the classes filling the gap between context-free languages and context-sensitive languages. They possess characterizations by a natural machine model, length-reducing two-pushdown automata (lrTPDA). We introduce a lower bound technique for lrTPDAs. Using this technique, we prove the conjecture of McNaughton, Narendran and Otto that the set of palindromes is not in CRL. As a consequence we obtain that CFL∩coCFL as well as UCFL∩coUCFL are not included in CRL, where UCFL denotes the class of unambiguous context-free languages; this solves an open problem posed by Beaudry, Holzer, Niemann and Otto. Another corollary is that CRL is a strict subset of GCSL∩coGCSL.

TCS Journal 2007 Journal Article

On complexity of grammars related to the safety problem

• Tomasz Jurdziński

Leftist grammars were introduced by Motwani et al. , who established the relationship between the complexity of the accessibility problem (or safety problem) for certain general protection systems and the membership problem for these grammars. The membership problem for leftist grammars is decidable. This implies the decidability of the accessibility problem. It is shown that the membership problem for leftist grammars is PSPACE-hard. Therefore, the accessibility problem in the appropriate protection systems is PSPACE-hard as well. Furthermore, the PSPACE-hardness result is adapted to a very restricted class of leftist grammars, if the grammar is a part of the input.

TCS Journal 2006 Journal Article

Restarting automata with restricted utilization of auxiliary symbols

• Tomasz Jurdziński
• Friedrich Otto

The restarting automaton is a restricted model of computation that was introduced by Jančar et al. to model the so-called analysis by reduction, which is a technique used in linguistics to analyse sentences of natural languages. The most general models of restarting automata make use of auxiliary symbols in their rewrite operations, although this ability does not directly correspond to any aspect of the analysis by reduction. Here we put restrictions on the way in which restarting automata use auxiliary symbols, and we investigate the influence of these restrictions on their expressive power. In fact, we consider two types of restrictions. First, we consider the number of auxiliary symbols in the tape alphabet of a restarting automaton as a measure of its descriptional complexity. Secondly, we consider the number of occurrences of auxiliary symbols on the tape as a dynamic complexity measure. We establish some lower and upper bounds with respect to these complexity measures concerning the ability of restarting automata to recognize the (deterministic) context-free languages and some of their subclasses.