Leslie G. Valiant
- 1 GINSBURG, S , AND GREIBACH, S A. Deterministic context-free languages. Inform and Contr 9 (1966), 620-668Google Scholar
- 2 GINSBURG, S., AND SPANIER, E Finite-turn pushdown automata SIAM J. Control ~ (1966), 423-434Google Scholar
- 3 HAa~ISON, M. A, AND HAVEL, I M. Strict deterministic grammars. J. Comput ~yst Sc~ 7 (1973) 237-277.Google Scholar
- 4 Hxa~isoN, M A., ASp HAV~L, I. M Real t~me strict deterministic languages. SIAM J Computsng I (1972) 333-349Google Scholar
- 5 KO~NJAK, A. J, AND HOPCROF% J E S~mple deterministic languages. IEEE 7th Symp. on Switching and Automata Theory, Berkeley, Calif., 1966, pp. 36-46.Google Scholar
- 6 LEwis, P. M Ii, AND STeARnS, R.E. Syntax-directed transductlon. J. ACM 15, 3 (July 1968), 465-488 Google Scholar
- 7 HEV~R, A. R, AND FISCHER, M J Economy of descriptmn by automata, grammars, and formal ~systems IEEE 12th Symp on Swltchlng and Automata Theory, 1971, 188-191.Google Scholar
- 8 ROSENXR~NTZ, D j, X~D STEARNS, R. E. Properties of deterministic topdown grammars. Inform. and Conlr 17 (1970) 226-255Google Scholar
- 9 ST~^RNS, R.E. A regularity test for pushdown machines. Inform and Cont. 11 (1967), 323-340Google Scholar
- 10 Vhu^~w, L. G Declsmn procedures for families of deterministic pushdown automata. Ph D. Th, Computer Centre Rep No. 7, U of Warwick, Coventry, England, 1973 Google Scholar
- 11 VALXANT, b. G. The eqmvalence problem for deterministic fimte-turn pushdown automata Inform. and Contr ~5 (1974), 123-133Google Scholar
- 12 VALIANT, L G. AN~ PATERSON, M S. Deterministic one-counter automata. J. Comput. ,Syst. Sc~. (to appear). Google Scholar
- 13 VALIANT, L.G. Manuscript.Google Scholar
Index Terms
- Regularity and Related Problems for Deterministic Pushdown Automata
Recommendations
Efficient determinization of visibly and height-deterministic pushdown automata
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 ...
Deterministic Pushdown Automata and Unary Languages
CIAA '08: Proceedings of the 13th international conference on Implementation and Applications of AutomataThe simulation of deterministic pushdown automata defined over a one letter alphabet by finite state automata is investigated from a descriptional complexity point of view. We show that each unary deterministic pushdown automaton of size s can be ...
Flip-pushdown automata: nondeterminism is better than determinism
DLT'03: Proceedings of the 7th international conference on Developments in language theoryFlip-pushdown automata are pushdown automata with the additional ability to flip or reverse its pushdown. We investigate deterministic and nondeterministic flip-pushdown automata accepting by final state or empty pushdown. In particular, for ...
Comments