A characterization of two-way deterministic of classes languages
- 1 October 1969
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02724847,p. 231-239
- https://doi.org/10.1109/swat.1969.1
Abstract
It is shown that a class of languages is defined by a class of two-way deterministic balloon automata if and only if that class is closed under marked union, marked Kleene closure and the inverse mappings performed by GSM's that move two ways on the input. Hence, the context sensitive languages and various time and tape complexity classes are equivalent to classes of 2DBA.Keywords
This publication has 5 references indexed in Scilit:
- Abstract families of processorsPublished by Association for Computing Machinery (ACM) ,1969
- Abstract families of deterministic languagesPublished by Association for Computing Machinery (ACM) ,1969
- Two-way balloon automata and AFLPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1968
- Abstract families of languagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1967
- The Reduction of Two-Way Automata to One-Way AutomataIBM Journal of Research and Development, 1959