TWO-WAY BALLOON AUTOMATA AND AFL,
Abstract
It is shown that if the family of languages accepted by a closed class of two-way balloon automata is closed under length-preserving homomorphism, then this family is an AFL closed under intersection and e-free substitution. It is then proved that the family of languages accepted by the closed class of two-way balloon automata of (nonerasing) (deterministic) stack acceptors is such a family. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 25, 1968
- Accession Number
- AD0668088
Entities
People
- John Hopcroft
- Seymour Ginsburg
Organizations
- System Development Corporation