New Results on Semilinear Sets and Variants of Jumping Finite Automata

Simon Beier

Diese Publikation zitieren

Simon Beier, New Results on Semilinear Sets and Variants of Jumping Finite Automata (2020), Logos Verlag, Berlin, ISBN: 9783832586447

Beschreibung / Abstract

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.

Inhaltsverzeichnis

  • BEGINN
  • I Preamble
  • 1 Introduction
  • 2 Basic Notions
  • 2.1 Monoids and Recognizable Subsets
  • 2.2 Operations
  • 2.3 Turing Machines
  • 2.4 Pushdown Automata
  • 2.5 Finite Automata
  • 2.6 Semilinear Sets
  • 2.7 Jumping Finite Automata
  • 2.8 Right One-Way Jumping Finite Automata
  • II Semilinear Sets
  • 3 Descriptional Complexity of Operations on Semilinear Sets
  • 3.1 Intersection
  • 3.2 Complementation
  • 3.3 Inverse Homomorphism
  • 4 Semirecognizable Sets
  • 4.1 Rational Cones and Semirecognizability of Linear Sets
  • 4.2 Rational Cones and Carath´eodory-Like Decompositions of Lattices
  • 4.3 Finite Unions of Semirecognizable Sets
  • 4.4 Parikh-Preimages of Semirecognizable Sets
  • III Variants of Jumping Finite Automata
  • 5 Operational State Complexity of Jumping Finite Automata
  • 5.1 Intersection
  • 5.2 Complementation
  • 5.3 Inverse Homomorphism
  • 5.4 Intersection with Regular Languages
  • 6 Properties of Right One-Way Jumping Finite Automata
  • 6.1 Permutation Closed Languages, ROWJFAs, and Semirecognizability
  • 6.2 Closure Properties of the Languages Accepted by ROWJFAs
  • 6.3 Concatenations of Languages
  • 7 Problems Involving Right One-Way Jumping Finite Automata
  • 7.1 Basic Properties
  • 7.2 Variants of the Word Problem
  • 7.3 ROWJFAs and Permutation Closed Languages
  • 8 Nondeterministic Right One-Way Jumping Finite Automata
  • 8.1 ROWJFAs with Multiple Initial States and Semirecognizability
  • 8.2 Nondeterministic ROWJFAs
  • 8.3 Nondeterministic ROWJFAs with Spontaneous Transitions
  • 8.4 Relations to Right-Revolving Finite Automata
  • 8.5 Relations to Finite-State Acceptors With Translucent Letters
  • IV Outro
  • 9 Conclusion and Directions for Further Research

Ähnliche Titel

    Mehr von diesem Autor