Publication result detail

On Parallel Versions of Jumping Finite Automata

KOCMAN, R.; MEDUNA, A.

Original Title

On Parallel Versions of Jumping Finite Automata

English Title

On Parallel Versions of Jumping Finite Automata

Type

Paper in proceedings (conference paper)

Original Abstract

The present paper proposes a new investigation area in automata theory -- n-parallel jumping finite automata. These automata further extend recently presented jumping finite automata that are focused on discontinuous reading. The proposed modification uses multiple reading heads that work in parallel and can discontinuously read from the input in several places at once. We also define the more restricted version of these automata which only allows jumping to the right. This restricted version is then further studied, compared with n-parallel right linear grammars, and several of its properties are derived.

English abstract

The present paper proposes a new investigation area in automata theory -- n-parallel jumping finite automata. These automata further extend recently presented jumping finite automata that are focused on discontinuous reading. The proposed modification uses multiple reading heads that work in parallel and can discontinuously read from the input in several places at once. We also define the more restricted version of these automata which only allows jumping to the right. This restricted version is then further studied, compared with n-parallel right linear grammars, and several of its properties are derived.

Keywords

jumping finite automata, n-parallel right linear grammars, discontinuous tape reading, parallel tape reading

Key words in English

jumping finite automata, n-parallel right linear grammars, discontinuous tape reading, parallel tape reading

Authors

KOCMAN, R.; MEDUNA, A.

RIV year

2017

Released

15.12.2016

Publisher

Springer International Publishing

Location

Cham

ISBN

978-3-319-46534-0

Book

Proceedings of the 2015 Federated Conference on Software Development and Object Technologies

Edition

Advances in Intelligent Systems and Computing

Volume

511

Pages from

142

Pages to

149

Pages count

8

URL

http://link.springer.com/chapter/10.1007/978-3-319-46535-7_12

BibTex

@inproceedings{BUT119917,
  author="Radim {Kocman} and Alexandr {Meduna}",
  title="On Parallel Versions of Jumping Finite Automata",
  booktitle="Proceedings of the 2015 Federated Conference on Software Development and Object Technologies",
  year="2016",
  series="Advances in Intelligent Systems and Computing",
  volume="511",
  pages="142--149",
  publisher="Springer International Publishing",
  address="Cham",
  doi="10.1007/978-3-319-46535-7\{_}12",
  isbn="978-3-319-46534-0",
  url="http://link.springer.com/chapter/10.1007/978-3-319-46535-7_12"
}

Documents

parallel-jfa