New Results on Semilinear Sets and Variants of Jumping Finite Automata

Simon Beier

ISBN 978-3-8325-5210-7
244 pages, year of publication: 2020
price: 41.00 €
In formal language theory, the Parikh-image describes the absolute frequencies of symbols in words of a given language. The Parikh-images of regular languages are the same as the ones of context-free languages. These kinds of sets are called semilinear. Another algebraically defined class of sets has played an important role since the early days of formal language theory: recognizable subsets of monoids are a generalization of regular languages. A set is recognizable if and only if its syntactic monoid is finite.

The first part of this monograph gives new results on semilinear sets. The descriptional complexity of operations is investigated. Semirecognizable subsets of monoids are introduced. Semirecognizability demands that the projection of the subset to its syntactic monoid is finite. The semirecognizable subsets of finitely generated free commutative monoids, which form a proper subset of the semilinear sets, are studied. Connections to rational cones enable the use of geometric methods.

Jumping finite automata are a model for discontinuous information processing that has attracted interest for some years. Their operational state complexity and a variant called right one-way jumping finite automata are explored in the second part. We show that a permutation closed language is accepted by this variant if and only if it is semirecognizable. Results from the first part are used to get a better insight into these devices.

cover cover cover cover cover cover cover cover cover
  • formal language theory
  • automata theory
  • semilinear sets
  • jumping finite automata
  • recognizable sets

Buying Options

41.00 €

39.00 €
51.00 €
55.00 €

(D) = Within Germany
(W) = Abroad

*You can purchase the eBook (PDF) alone or combined with the printed book (eBundle). In both cases we use the payment service of PayPal for charging you - nevertheless it is not necessary to have a PayPal-account. With purchasing the eBook or eBundle you accept our licence for eBooks.

For multi-user or campus licences (MyLibrary) please fill in the form or write an email to