One-way stack automata

1967223 citationsJournal Articlebronze Open Access

Authors

Sheila A. Greibach · Harvard University Press

Michael A. Harrison · University of California, Berkeley

Abstract

A number of operations which either preserve sets accepted by one-way stack automata or preserve sets accepted by deterministic one-way stack automata are presented. For example, sequential transduction preserves the former; set complementation, the latter. Several solvability questions are also considered.

Topics & Keywords

semigroups and automata theory Advanced Algebra and Logic Formal Methods in Verification

Publication Details

Published in: Journal of the ACM

Volume 14, Issue 2, pp. 389-418

DOI: 10.1145/321386.321403

Field-Weighted Citation Impact: 20.32

Command Palette

One-way stack automata

Authors

Abstract

Topics & Keywords

Publication Details