Source author record

Julius Jonušas

Julius Jonušas appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Logic in Computer Science math.GR math.LO math.RA Computational Complexity math.DS

Catalog footprint

What is connected

5works

6topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2021arXiv

Pseudo-loop conditions

We initiate the systematic study of loop conditions of arbitrary finite width. Each loop condition is a finite set of identities of a particular shape, and satisfaction of these identities in an algebra is characterized by it forcing a constant tuple into certain invariant relations on powers of the algebra. By showing the equivalence of various loop conditions, we are able to provide a new and short proof of the recent celebrated result stating the existence of a weakest non-trivial idempotent strong Mal'cev condition. We then consider pseudo-loop conditions, a modification suitable for oligomorphic algebras, and show the equivalence of various pseudo-loop conditions within this context. This allows us to provide a new and short proof of the fact that the satisfaction of non-trivial identities of height 1 in a closed oligomorphic core implies the satisfaction of a fixed single identity.

preprint2021arXiv

When symmetries are not enough: a hierarchy of hard Constraint Satisfaction Problems

We produce a class of $ω$-categorical structures with finite signature by applying a model-theoretic construction -- a refinement of the Hrushosvki-encoding -- to $ω$-categorical structures in a possibly infinite signature. We show that the encoded structures retain desirable algebraic properties of the original structures, but that the constraint satisfaction problems (CSPs) associated with these structures can be badly behaved in terms of computational complexity. This method allows us to systematically generate $ω$-categorical templates whose CSPs are complete for a variety of complexity classes of arbitrarily high complexity, and $ω$-categorical templates that show that membership in any given complexity class cannot be expressed by a set of identities on the polymorphisms. It moreover enables us to prove that recent results about the relevance of topology on polymorphism clones of $ω$-categorical structures also apply for CSP templates, i.e., structures in a finite language. Finally, we obtain a concrete algebraic criterion which could constitute a description of the delineation between tractability and NP-hardness in the dichotomy conjecture for first-order reducts of finitely bounded homogeneous structures.

preprint2020arXiv

Generating the monoid of $2 \times 2$ matrices over max-plus and min-plus semirings

In this short note, we describe generating sets for the monoids of consisting of all $2 \times 2$ matrices over certain finite tropical semirings.

preprint2014arXiv

Some isomorphism results for Thompson like groups $V_n(G)$

We consider a class of groups $V_n(G)$ which are supergroups of the Higman-Thompson groups $V_n$. These groups fit in a framework of Elizabeth Scott for generating infinite virtually simple groups, and the groups we study in particular are initially introduced by Farley and Hughes. The group $V_n(G)$ is the result one obtains by taking the $V_n$ generators and adding a tree automorphism for each generator of a subgroup $G$ of the symmetric group on $n$ letters, where the new generators each permute the child leaves of a specific vertex $α$ of the infinite rooted $n$-ary tree according to the permutation they represent, and then they iterate this permutation again at each vertex which is a descendent of $α$. Farley and Hughes show that $V_n(G)$ is not isomorphic to $V_n$ when $G$ fails to act freely on the points $\{1,2,...,n\}$, and expect further non-isomorphism results in the other cases. We show the perhaps surprising result that if $G$ does act freely, then $V_n(G)\cong V_n$. We also generalise these results and produce some examples of even more isomorphisms amongst groups in the family $V_n(G)$. Essential tools in the above work are a study of the dynamics of the action of elements of $V_n(G)$ on Cantor space, Rubin's Theorem, and transducers from Grigorchuk, Nekrashevych, and Suschanskiĭ's rational group on the $n$-ary alphabet.

preprint2013arXiv

A finite interval in the subsemigroup lattice of the full transformation monoid

In this paper we describe a portion of the subsemigroup lattice of the \emph{full transformation semigroup} $Ω^Ω$, which consists of all mappings on the countable infinite set $Ω$. Gavrilov showed that there are five maximal subsemigroups of $Ω^Ω$ containing the symmetric group $\sym(Ω)$. The portion of the subsemigroup lattice of $Ω^Ω$ which we describe is that between the intersection of these five maximal subsemigroups and $Ω^Ω$. We prove that there are only 38 subsemigroups in this interval, in contrast to the $2^{2^{\aleph_0}}$ subsemigroups between $\sym(Ω)$ and $Ω^Ω$.