ARTÍCULO
TITULO

Some more on omega-finite automata and omega-regular languages. Part I: The main definitions and properties

Boris Melnikov    
Aleksandra Melnikova    

Resumen

The finite and infinite iterations of finite and infinite languages arise in various problems of the formal languages theory.For instance, we can mention their application for the description of subclasses of the context-free languages class with the decidable equivalence problem.For infinite iterations of finite languages, we consider in this paper so-called strongly connected omega-automata and corresponding omega-regular languages.For them, many statements are fulfilled that are not satisfied in the more general case, i.e. when we use arbitrary omega-finite automata and corresponding omega-regular languages; the omega-iterations of languages include in the class of strongly connected omega-regular languages.The main of such properties and statements are non-existence of an omega-automaton for which there is no equivalent deterministic, and the possibility of checking the equivalence of two given omega-automata; in the general case (i.e., when we consider arbitrary omega-automata), both of these properties are not satisfied.We also describe transferring the usual procedure of determinization to the case of omega-automata and show the correctness of this procedure in the cases we are considering.We consider some examples, and in the second part of the paper, we shall consider the transfer of a well-known example (so called Waterloo automaton) to the case of omega-automata and omega-languages.

 Artículos similares

       
 
Santa Vallejo Figueroa, Valeria Nava Lozano     Pág. 1 - 21
Nowadays documents are the main way to represent information and knowledge in several domains. Continuously users store documents in hard disk or online media according to some personal organization based on topics, but such documents can contain one or ... ver más

 
Yugen Yi, Haoming Zhang, Ningyi Zhang, Wei Zhou, Xiaomei Huang, Gengsheng Xie and Caixia Zheng    
As the feature dimension of data continues to expand, the task of selecting an optimal subset of features from a pool of limited labeled data and extensive unlabeled data becomes more and more challenging. In recent years, some semi-supervised feature se... ver más
Revista: Information

 
Deyuan Zhong, Liangda Fang and Quanlong Guan    
Encoding a dictionary into another representation means that all the words can be stored in the dictionary in a more efficient way. In this way, we can complete common operations in dictionaries, such as (1) searching for a word in the dictionary, (2) ad... ver más
Revista: Algorithms

 
Luis M. de Campos, Juan M. Fernández-Luna, Juan F. Huete, Francisco J. Ribadas-Pena and Néstor Bolaños    
In the context of academic expert finding, this paper investigates and compares the performance of information retrieval (IR) and machine learning (ML) methods, including deep learning, to approach the problem of identifying academic figures who are expe... ver más
Revista: Algorithms

 
Aniket Kumar Singh, Bishal Lamichhane, Suman Devkota, Uttam Dhakal and Chandra Dhakal    
This study investigates self-assessment tendencies in Large Language Models (LLMs), examining if patterns resemble human cognitive biases like the Dunning?Kruger effect. LLMs, including GPT, BARD, Claude, and LLaMA, are evaluated using confidence scores ... ver más
Revista: Information