Author name cluster

Nik Ruškuc

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

1 author row

TCS Journal 2016 Journal Article

On the star-height of subword counting languages and their relationship to Rees zero-matrix semigroups

Tom Bourne
Nik Ruškuc

Given a word w over a finite alphabet, we consider, in three special cases, the generalised star-height of the languages in which w occurs as a contiguous subword (factor) an exact number of times and of the languages in which w occurs as a contiguous subword modulo a fixed number, and prove that in each case it is at most one. We use these combinatorial results to show that any language recognised by a Rees (zero-)matrix semigroup over an Abelian group is of generalised star-height at most one.

Details DOI

I&C Journal 2009 Journal Article

Automatic presentations for semigroups

Alan J. Cain
Graham Oliver
Nik Ruškuc
Richard M. Thomas

This paper applies the concept of FA-presentable structures to semigroups. We give a complete classification of the finitely generated FA-presentable cancellative semigroups: namely, a finitely generated cancellative semigroup is FA-presentable if and only if it is a subsemigroup of a virtually abelian group. We prove that all finitely generated commutative semigroups are FA-presentable. We give a complete list of FA-presentable one-relation semigroups and compare the classes of FA-presentable semigroups and automatic semigroups.

Details DOI

TCS Journal 2008 Journal Article

Simple permutations: Decidability and unavoidable substructures

Robert Brignall
Nik Ruškuc
Vincent Vatter

We prove that it is decidable whether a finitely based permutation class contains infinitely many simple permutations, and establish an unavoidable substructure result for simple permutations: every sufficiently long simple permutation contains an alternation or oscillation of length k.

Details DOI