New Results on Semilinear Sets and Variants of Jumping Finite Automata
By (author) Simon Beier
Paperback (Published)
(November 2020)
ISBN: 9783832552107
5.71 x 8.27 inches
Price: $62.00
In stock
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.
- By (author) Simon Beier
Similar Books
Punning in Odd or Elegant Constructions in Jeremiah
The Convergence of Linguistics, Rhetoric, and Textuality in the Hebrew Text of Jeremiah
Care in an Era of New Technologies and Artificial Intelligence
Relationships in a Connected World
Volume 14
Language, Semantics, and Cognition in Ancient Egypt and Beyond
Proceedings of the International Conference, Yale University, April 16-18, 2021
Volume 14
Linguistic Fragmentation and Cultural Inclusion in the Middle Ages
Translation, Plurilingualism, Multilingualism
Volume 22
