- 1 GINSBURGB, S., AND RICE, H.G. Two families of LangUAges related to ALGOL. J. ACM 9 (1962), 350-371. Google Scholar
- 2 --- AND ROSE, G. F. Operations which preserve definability in languages. J. ACM 10 (1963), 175-195. Google Scholar
- 3 --.-- AND ... . Some recursively unsolvable problems in ALGOL-like languages. J. ACM I0 (1963), 2,c47. Google Scholar
- 4 KoNIG, D. Theorie Der Endlichen und Unencltichen Graphen. CheIsea Publishing Co, New York, 1950.Google Scholar
- 5 RABINs, M., AND SCOTT, D. Finite automata and their decision problems. IBM Y. research Devsl. 3 (1959), 115-125.Google Scholar
- 6 YNGVE, V. A model and tm hypothesis for language structure. Proc. Am. Philos. Soc. lO4 (1960), 444-466.Google Scholar
- 7 ---- Comupter programs for translation. Sci, Am. 206' (June 1962), 68-76.Google Scholar
Index Terms
- Solvability of Machine Mappings of Regular Sets to Regular Sets
Recommendations
Boundary sets of regular and context-free languages
We investigate the descriptional and computational complexity of boundary sets of regular and context-free languages. For a letter a, the right (left, respectively) a-boundary set of a language L consists of the words in L whose a-predecessor or a-...
Regular sets over extended tree structures
We investigate notions of decidability and definability for the Monadic Second-Order Logic over labeled tree structures, and its relations with finite automata using oracles to test input prefixes. A general framework is defined allowing to transfer ...
Regular Transducer Expressions for Regular Transformations
LICS '18: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer ScienceFunctional MSO transductions, deterministic two-way transducers, as well as streaming string transducers are all equivalent models for regular functions. In this paper, we show that every regular function, either on finite words or on infinite words, ...
Comments