Paper Info
Title
Efficient determinization of visibly and height-deterministic pushdown automata.
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. HighlightsTracking 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.
Year
DOI
Venue
2016
10.1016/j.cl.2016.07.005
Computer Languages, Systems & Structures
Keywords
Field
DocType
Pushdown automata,Visibly pushdown automata,Height-deterministic pushdown automata,Deterministic pushdown automata,Determinization
Deterministic context-free grammar,Embedded pushdown automaton,Context-free language,Programming language,Nondeterministic algorithm,Nested word,Computer science,Deterministic pushdown automaton,Deterministic context-free language,Theoretical computer science,Pushdown automaton
Journal
Volume
Issue
ISSN
46
C
1477-8424
Citations 
PageRank 
References 
0
0.34
0
Authors
4
Name
Order
Citations
PageRank
Radomír Polách101.01
Jan Travnicek211.72
Jan Janousek383.74
Bořivoj Melichar427617.21