In formal language theory, a cone (also known as a full trio) is a set of formal languages that possesses certain closure properties exhibited by well-known families of languages, including the regular languages, context-free languages, and recursively enumerable languages. The concept provides an abstract framework that subsumes these families under a common structural definition. A related concept is the faithful cone (or simply trio), which has somewhat weaker closure conditions.
Definition
A cone is a family $ \mathcal{S} $ of languages such that $ \mathcal{S} $ contains at least one non-empty language, and for any language $ L \in \mathcal{S} $ over some alphabet $ \Sigma $, the following three closure properties hold:
- Homomorphism: If $ h $ is a homomorphism from $ \Sigma^* $ to $ \Delta^* $, then the language $ h(L) $ is in $ \mathcal{S} $.
- Inverse homomorphism: If $ h $ is a homomorphism from some $ \Delta^* $ to $ \Sigma^* $, then the language $ h^{-1}(L) $ is in $ \mathcal{S} $.
- Intersection with regular languages: If $ R $ is any regular language over $ \Sigma $, then $ L \cap R $ is in $ \mathcal{S} $.
The family of all regular languages is contained in any cone.
If the definition is restricted to homomorphisms that do not map any symbol to the empty word (i.e., non-erasing homomorphisms), the resulting structure is called a faithful cone (or trio). Inverse homomorphisms are not restricted in this case.
Examples in the Chomsky Hierarchy
- Regular languages form a cone.
- Context-free languages form a cone.
- Recursively enumerable languages form a cone.
- Context-sensitive languages form only a faithful cone (not a full cone).
- Recursive languages form only a faithful cone (not a full cone).
Relation to Finite State Transducers
A family of languages is a cone if and only if it is closed under finite state transductions. Each of the three cone operations (homomorphism, inverse homomorphism, and intersection with a regular language) can be implemented using a finite state transducer. Since finite state transducers are closed under composition, any sequence of cone operations can be performed by a single finite state transducer.
Conversely, every finite state transduction $ T $ can be decomposed into cone operations. This decomposition is captured by Nivat's Theorem: every such transduction can be effectively expressed as $ T(L) = g(h^{-1}(L) \cap R) $, where $ g $ and $ h $ are homomorphisms and $ R $ is a regular language depending only on $ T $.
Terminology
The term cone has French origins. In the English-language literature, the term full trio is more commonly used, with trio corresponding to the faithful cone.
See Also
- Abstract family of languages (AFL)
References
- Ginsburg, Seymour; Greibach, Sheila (1967). "Abstract Families of Languages". Conference Record of 1967 Eighth Annual Symposium on Switching and Automata Theory. IEEE. pp. 128–139.
- Nivat, Maurice (1968). "Transductions des langages de Chomsky". Annales de l'Institut Fourier. 18 (1): 339–455.
- Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. Chapter 11.
- Mateescu, Alexandru; Salomaa, Arto (1997). "Chapter 4: Aspects of Classical Language Theory". In Rozenberg, Grzegorz; Salomaa, Arto (eds.). Handbook of Formal Languages. Volume I: Word, language, grammar. Springer-Verlag. pp. 175–252.
