Efficient determinization of visibly and height-deterministic pushdown automata. (November 2016)

• Record Type: Journal Article
• Authors: Polách, Radomír; Trávníček, Jan; Janoušek, Jan; Melichar, Bořivoj
• Is Part Of: Computer languages, systems & structures. Volume 46(2016)
• Page Start: 91
• Page End: 105
• Publication Date: 2016-11
• Subjects: Pushdown automata -- Visibly pushdown automata -- Height-deterministic pushdown automata -- Deterministic pushdown automata -- Determinization; Programming languages (Electronic computers) -- Periodicals; Computer networks -- Periodicals; Computer architecture -- Periodicals; Computer systems -- Periodicals; Langage de programmation; Réseau d'ordinateurs; Architecture d'ordinateur; Périodique électronique (Descripteur de forme); Ressource Internet (Descripteur de forme); 005.13
• DOI: 10.1016/j.cl.2016.07.005
• Languages: English
• ISSNs: 1477-8424

Abstract

Abstract: New algorithms for the determinization of nondeterministic visibly and nondeterministic real-time height-deterministic pushdown automata are presented. The algorithms improve the results of existing algorithms. They construct only accessible states and necessary pushdown symbols of the resulting deterministic pushdown automata. Abstract : Highlights: Tracking pushdown symbols which can appear on top of pushdown store for each state. Generating pop (return) transition only for possible top pushdown symbols for each state. Overall generating only accessible states and necessary pushdown store symbols. Visibly pushdown automata determinization algorithm. Height-deterministic (real-time) automata determinization algorithm.