FB 07 - Mathematik und Informatik, Physik, Geographie

Dauerhafte URI für den Bereich

jlupub.ub.uni-giessen.de/handle/jlupub/1037

Stöbern nach

Auflistung FB 07 - Mathematik und Informatik, Physik, Geographie nach Autor:in "Beier, Simon"

Gerade angezeigt 1 - 3 von 3
  • Vorschaubild
    Item
    On the descriptional complexity of operations on semilinear sets
    (2017) Beier, Simon; Holzer, Markus; Kutrib, Martin
    We investigate the descriptional complexity of operations on semilinear sets. Roughly speaking, a semilinear set is the finite union of linear sets, which are built by constant and period vectors. The interesting parameters of a semilinear set are: (i) the maximal value that appears in the vectors of periods and constants and (ii) the number of such sets of periods and constants necessary to describe the semilinear set under consideration. More precisely, we prove upper bounds on the union, intersection, complementation, and inverse homomorphism. In particular, our result on the complementation upper bound answers an open problem from [G. J. Lavado, G. Pighizzini, S. Seki: Operational State Complexity of Parikh Equivalence, 2014].
  • Vorschaubild
    Item
    Properties of right one-way jumping finite automata
    (2018) Beier, Simon; Holzer, Markus
    Right one-way jumping finite automata (ROWJFAs), were recently introduced in [H. Chigahara, S.Z. Fazekas, A. Yamamura: One-Way Jumping Finite Automata, Internat. J. Found. Comput. Sci., 27(3), 2016] and are jumping automata that process the input in a discontinuous way with the restriction that the input head reads deterministically from left-to-right starting from the leftmost letter in the input and when it reaches the end of the input word, it returns to the beginning and continues the computation. We solve most of the open problems of these devices. In particular, we characterize the family of permutation closed languages accepted by ROWJFAs in terms of Myhill-Nerode equivalence classes. Using this, we investigate closure and non-closure properties as well as inclusion relations to other language families. We also give more characterizations of languages accepted by ROWJFAs for some interesting cases.
  • Vorschaubild
    Item
    Semi-Linear Lattices and Right One-Way Jumping Finite Automata
    (2019) Beier, Simon; Holzer, Markus
    Right one-way jumping automata (ROWJFAs) are an automaton model that was recently introduced for processing the input in a discontinuous way. In [S. Beier, M. Holzer: Properties of right one-way jumping finite automata. In Proc. 20th DCFS, number 10952 in LNCS, 2018] it was shown that the permutation closed languages accepted by ROWJFAs are exactly that with a finite number of positive Myhill-Nerode classes. Here a Myhill-Nerode equivalence class [w]_L of a language L is said to be positive if w belongs to L. Obviously, this notion of positive Myhill-Nerode classes generalizes to sets of vectors of natural numbers. We give a characterization of the linear sets of vectors with a finite number of positive Myhill-Nerode classes, which uses rational cones. Furthermore, we investigate when a set of vectors can be decomposed as a finite union of sets of vectors with a finite number of positive Myhill-Nerode classes. A crucial role play lattices, which are special semi-linear sets that are defined as a natural way to extend ´the pattern´ of a linear set to the whole set of vectors of natural numbers in a given dimension. We show deep connections of lattices to the Myhill-Nerode relation and to rational cones. Some of these results will be used to give characterization results about ROWJFAs with multiple initial states. For binary alphabets we show connections of these and related automata to counter automata.