Detail publikačního výsledku

Jumping Finite Automata

MEDUNA, A.; ZEMEK, P.

Originální název

Jumping Finite Automata

Anglický název

Jumping Finite Automata

Druh

Článek WoS

Originální abstrakt

The present paper proposes a new investigation area in automata theory: jumping finite automata. These automata work like classical finite automata except that they read input words discontinuously; that is, after reading a symbol, they can jump over some symbols within the words and continue their computation from there. The paper establishes several results concerning jumping finite automata in terms of commonly investigated areas of automata theory, such as decidability and closure properties. Most importantly, it achieves several results that demonstrate differences between jumping finite automata and classical finite automata. In its conclusion, the paper formulates several open problems and suggests future investigation areas.

Anglický abstrakt

The present paper proposes a new investigation area in automata theory: jumping finite automata. These automata work like classical finite automata except that they read input words discontinuously; that is, after reading a symbol, they can jump over some symbols within the words and continue their computation from there. The paper establishes several results concerning jumping finite automata in terms of commonly investigated areas of automata theory, such as decidability and closure properties. Most importantly, it achieves several results that demonstrate differences between jumping finite automata and classical finite automata. In its conclusion, the paper formulates several open problems and suggests future investigation areas.

Klíčová slova

modified finite automata, discontinuous tape reading, basic properties, comparison with classical finite automata, perspectives

Klíčová slova v angličtině

modified finite automata, discontinuous tape reading, basic properties, comparison with classical finite automata, perspectives

Autoři

MEDUNA, A.; ZEMEK, P.

Rok RIV

2013

Vydáno

01.11.2012

ISSN

0129-0541

Periodikum

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

Svazek

23

Číslo

7

Stát

Singapurská republika

Strany od

1555

Strany do

1578

Strany počet

24

URL

http://dx.doi.org/10.1142/S0129054112500244

BibTex

@article{BUT98563,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="Jumping Finite Automata",
  journal="INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE",
  year="2012",
  volume="23",
  number="7",
  pages="1555--1578",
  doi="10.1142/S0129054112500244",
  issn="0129-0541",
  url="http://dx.doi.org/10.1142/S0129054112500244"
}