Author name cluster

Adam Malinowski

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

LPAR Conference 2020 Conference Paper

The Triguarded Fragment with Transitivity

Emanuel Kieronski
Adam Malinowski

The triguarded fragment of first-order logic is an extension of the guarded fragment in which quantification for subformulas with at most two free variables need not be guarded. Thus, it unifies two prominent decidable logics: the guarded fragment and the two-variable fragment. Its satisfiability problem is known to be undecidable in the presence of equality, but becomes decidable when equality is forbidden. We consider an extension of the tri- guarded fragment without equality by transitive relations, allowing them to be used only as guards. We show that the satisfiability problem for the obtained formalism is decidable and 2-ExpTime-complete, that is, it is of the same complexity as for the analogous exten- sion of the classical guarded fragment. In fact, in our satisfiability test we use a decision procedure for the latter as a subroutine. We also show how our approach, consisting in exploiting some existing results on guarded logics, can be used to reprove some known facts, as well as to derive some other new results on triguarded logics.

Details

TCS Journal 2008 Journal Article

How to meet in anonymous network

Dariusz R. Kowalski
Adam Malinowski

A set of k mobile agents with distinct identifiers and located in nodes of an unknown anonymous connected network, have to meet at some node. We show that this gathering problem is no harder than its special case for k = 2, called the rendezvous problem, and design deterministic protocols solving the rendezvous problem with arbitrary startups in rings and in general networks. The measure of performance is the number of steps since the startup of the last agent until the rendezvous is achieved. For rings we design an oblivious protocol with cost O ( n log ℓ ), where n is the size of the network and ℓ is the minimum label of participating agents. This result is asymptotically optimal due to the lower bound showed by [A. Dessmark, P. Fraigniaud, D. Kowalski, A. Pelc, Deterministic rendezvous in graphs, Algorithmica 46 (2006) 69–96]. For general networks we show a protocol with cost polynomial in n and log ℓ, independent of the maximum difference τ of startup times, which answers in the affirmative the open question by [A. Dessmark, P. Fraigniaud, D. Kowalski, A. Pelc, Deterministic rendezvous in graphs, Algorithmica 46 (2006) 69–96].

Details DOI

TCS Journal 1995 Journal Article

Anonymous wireless rings

Krzysztof Diks
Evangelos Kranakis
Adam Malinowski
Andrzej Pelc

We introduce anonymous wireless rings: a new computational model for ring networks. In the well-known hardware ring each processor has two buffers, one corresponding to each of its neighbors. In the wireless ring each processor has a single buffer and cannot distinguish which neighbor the arriving bit comes from. This feature substantially increases anonymity of the ring. A priori it is not clear whether any nontrivial computation can be performed on wireless rings. Nevertheless we show that wireless rings are computationally equivalent to hardware rings.

Details DOI