Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Semi-Linear Lattices and Right One-Way Jumping Finite Automata

Beier, Simon ; Holzer, Markus

Zum Volltext im pdf-Format: Dokument 1.pdf (1.578 KB)

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-144335

Freie Schlagwörter (Englisch): Right One-Way Jumping Finite Automata , Semi-Linear Sets and Lattices , Rational Cones , Myhill-Nerode Classes , Permutation Closed Languages
MSC - Klassifikation: 68Q05 , 68Q45 , 68Q10 , 15A03
Universität Justus-Liebig-Universit├Ąt Gie├čen
Institut: Institut f├╝r Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper
Zeitschrift, Serie: IFIG Research Report ; 1901
Sprache: Englisch
Erstellungsjahr: 2019
Publikationsdatum: 17.04.2019
Kurzfassung auf Englisch: 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.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand