Detail publikace

Jumping Finite Automata

MEDUNA, A. ZEMEK, P.

Originální název

Jumping Finite Automata

Anglický název

Jumping Finite Automata

Jazyk

en

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.

Dokumenty

BibTex 


@article{BUT98563,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="Jumping Finite Automata",
  annote="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.",
  address="NEUVEDEN",
  chapter="98563",
  doi="10.1142/S0129054112500244",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  number="7",
  volume="23",
  year="2012",
  month="november",
  pages="1555--1578",
  publisher="NEUVEDEN",
  type="journal article in Web of Science"
}