Romanian Journal of Information Science and Technology (ROMJIST)

An open – access publication

  |  HOME  |   GENERAL INFORMATION  |   ROMJIST ON-LINE  |  KEY INFORMATION FOR AUTHORS  |   COMMITTEES  |  

ROMJIST is a publication of Romanian Academy,
Section for Information Science and Technology

Editor – in – Chief:
Radu-Emil Precup

Honorary Co-Editors-in-Chief:
Horia-Nicolai Teodorescu
Gheorghe Stefan

Secretariate (office):
Adriana Apostol
Adress for correspondence: romjist@nano-link.net (after 1st of January, 2019)

Founding Editor-in-Chief
(until 10th of February, 2021):
Dan Dascalu

Editing of the printed version: Mihaela Marian (Publishing House of the Romanian Academy, Bucharest)

Technical editor
of the on-line version:
Lucian Milea (University POLITEHNICA of Bucharest)

Sponsor:
• National Institute for R & D
in Microtechnologies
(IMT Bucharest), www.imt.ro

ROMJIST Volume 21, No. 3, 2018, pp. 232-237
 

L. Charvat, A. Meduna
Internally Expandable Pushdown Automata and Their Computational Completeness

ABSTRACT: The present paper defines the notion of an internally expandable pushdown automaton (IEPDA). In essence, this automaton expands the topmost expandable non-input symbol in its pushdown list. This expanded symbol, however, may not occur on the very top of the pushdown; instead, it may appear deeper in the pushdown. The paper demonstrates that this notion represents an automaton-based counter part to the notion of a state grammar. Indeed, both are equally powerful. Therefore, internally expandable pushdown automata are computationally complete--that is, they are as powerful as Turing machines. In fact there are computationally complete IEPDAs with no more than four states

KEYWORDS: -

Read full text (pdf)






  |  HOME  |   GENERAL INFORMATION  |   ROMJIST ON-LINE  |  KEY INFORMATION FOR AUTHORS  |   COMMITTEES  |