Detail publikace

Regulated Pushdown Automata

Originální název

Regulated Pushdown Automata

Anglický název

Regulated Pushdown Automata

Jazyk

en

Originální abstrakt

The paper suggests a new investigation area of the formal language theory - regulated automata. Specifically, it investigates pushdown automata that regulate the use of their rules by control languages. It proves that this regulation has no effect on the power of pushdown automata if the control languages are regular. However, the pushdown automata regulated by linear control languages characterize the family of recursively enumerable languages.

Anglický abstrakt

The paper suggests a new investigation area of the formal language theory - regulated automata. Specifically, it investigates pushdown automata that regulate the use of their rules by control languages. It proves that this regulation has no effect on the power of pushdown automata if the control languages are regular. However, the pushdown automata regulated by linear control languages characterize the family of recursively enumerable languages.

Dokumenty

BibTex


@article{BUT40357,
  author="Dušan {Kolář} and Alexandr {Meduna}",
  title="Regulated Pushdown Automata",
  annote="The paper suggests a new investigation area of the formal language
theory - regulated automata. Specifically, it investigates pushdown
automata that regulate the use of their rules by control languages. It
proves that this regulation has no effect on the power of pushdown
automata if the
control languages are regular. However, the pushdown automata regulated
by
linear control languages characterize the family of recursively
enumerable
languages.",
  address="unknown",
  booktitle="Acta Cybernetica",
  chapter="40357",
  institution="unknown",
  number="4",
  volume="2000",
  year="2000",
  month="january",
  pages="653--664",
  publisher="unknown",
  type="journal article - other"
}