Publication detail

On State-Synchronized Automata Systems

KUČERA, J. MEDUNA, A.

Original Title

On State-Synchronized Automata Systems

English Title

On State-Synchronized Automata Systems

Type

journal article in Scopus

Language

en

Original Abstract

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.

English abstract

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.

Keywords

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

Released

11.05.2016

Publisher

NEUVEDEN

Location

NEUVEDEN

Pages from

221

Pages to

237

Pages count

17

URL

BibTex


@article{BUT130905,
  author="Jiří {Kučera} and Alexandr {Meduna}",
  title="On State-Synchronized Automata Systems",
  annote="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.",
  address="NEUVEDEN",
  chapter="130905",
  doi="10.4467/20838476SI.16.019.4360",
  edition="NEUVEDEN",
  howpublished="online",
  institution="NEUVEDEN",
  number="24",
  volume="2015",
  year="2016",
  month="may",
  pages="221--237",
  publisher="NEUVEDEN",
  type="journal article in Scopus"
}