Languages for defining sets in arbitrary algebras
- 1 October 1971
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02724847,p. 192-201
- https://doi.org/10.1109/swat.1971.16
Abstract
This paper presents a self-contained and more elementary treatment of our mathematical theory of the syntax and semantics of language developed in [W-1] and [ W-2]. It applies this theory to the definition of subsets, and operators on subsets of the carrier of algebras. We show how regular and context-free sets of strings, recognizable sets of trees, and recursively enumerable (r.e.) sets of natural numbers or strings can be defined in a "natural" algebraic manner which defines "similar" types of sets for arbitrary algebras. We employ our mathematical framework to develop semantic and syntactic normal form theorems which explicate the relationship between different languages which define the same classes of sets and operators. We also investigate the relationship between our languages and the earlier work of Mezei, Eilenberg and Wright [M-W], [E-W] and the work of Eilenberg and Elgot [E-E].Keywords
This publication has 7 references indexed in Scilit:
- Translating recursion equations into flow chartsJournal of Computer and System Sciences, 1971
- An algebraic theory of recursive definitions and recursive languagesPublished by Association for Computing Machinery (ACM) ,1971
- The lattice of flow diagramsPublished by Springer Nature ,1971
- Automata in general algebrasInformation and Control, 1967
- Algebraic automata and context-free setsInformation and Control, 1967
- A lattice-theoretical fixpoint theorem and its applicationsPacific Journal of Mathematics, 1955
- Effective operations on partial recursive functionsMathematical Logic Quarterly, 1955