Detail publikačního výsledku

On State-Synchronized Automata Systems

KUČERA, J.; MEDUNA, A.

Originální název

On State-Synchronized Automata Systems

Anglický název

On State-Synchronized Automata Systems

Druh

Článek Scopus

Originální abstrakt

In this paper, we introduce a new kind of automata systems, called state-synchronized automata systems of degree n.
In general, they consists of n pushdown automata, referred to as their components. These systems can perform a computation step provided that the concatenation of the current states of all their components belongs to a prescribed control language. As its main result, the paper demonstrates that these systems characterize the family of recursively enumerable languages. In fact, this characterization is demostrated in both deterministic and nondeterministic versions of these systems. Restricting their components, these systems provides less computational power.

Anglický abstrakt

In this paper, we introduce a new kind of automata systems, called state-synchronized automata systems of degree n.
In general, they consists of n pushdown automata, referred to as their components. These systems can perform a computation step provided that the concatenation of the current states of all their components belongs to a prescribed control language. As its main result, the paper demonstrates that these systems characterize the family of recursively enumerable languages. In fact, this characterization is demostrated in both deterministic and nondeterministic versions of these systems. Restricting their components, these systems provides less computational power.

Klíčová slova

state-synchronized automata systems, automata systems, pushdown automata, determinism, recursively enumerable languages

Klíčová slova v angličtině

state-synchronized automata systems, automata systems, pushdown automata, determinism, recursively enumerable languages

Autoři

KUČERA, J.; MEDUNA, A.

Rok RIV

2017

Vydáno

11.05.2016

ISSN

0860-0295

Periodikum

Schedae Informaticae

Svazek

2015

Číslo

24

Stát

Polská republika

Strany od

221

Strany do

237

Strany počet

17

URL

http://www.ejournals.eu/Schedae-Informaticae/2015/Volume-24/art/7023/

BibTex

@article{BUT130905,
  author="Jiří {Kučera} and Alexandr {Meduna}",
  title="On State-Synchronized Automata Systems",
  journal="Schedae Informaticae",
  year="2016",
  volume="2015",
  number="24",
  pages="221--237",
  doi="10.4467/20838476SI.16.019.4360",
  issn="0860-0295",
  url="http://www.ejournals.eu/Schedae-Informaticae/2015/Volume-24/art/7023/"
}

Dokumenty

2015_amjk_on_state-synchronized_automata_systems