Approximate NFA Universality Motivated by Information Theory

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2022

Autores

Konstantinidis, S (Autor) Outra; Mastnak, M (Autor) Outra; Nelma Moreira (Autor) FCUP; Rogério Reis (Autor) FCUP

Ata de Conferência Internacional

Título: DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2022

Páginas: 142-154

24th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems (DCFS)

Univ Debrecen, Debrecen, HUNGARY, AUG 29-31, 2022

Indexação

ISI Web of Knowledge - 1 Citação

Scopus - 1 Citação

Outras Informações

ID Authenticus: P-00X-4RQ

DOI: 10.1007/978-3-031-13257-5_11

Abstract (EN): In coding and information theory, it is desirable to construct maximal codes that can be either variable length codes or error control codes of fixed length. However deciding code maximality boils down to deciding whether a given NFA is universal, and this is a hard problem (including the case of whether the NFA accepts all words of a fixed length). On the other hand, it is acceptable to know whether a code is `approximately' maximal, which then boils down to whether a given NFA is 'approximately' universal. Here we introduce the notion of a (1 - epsilon)universal automaton and present polynomial randomized approximation algorithms to test NFA universality and related hard automata problems, for certain natural probability distributions on the set of words. We also conclude that the randomization aspect is necessary, as approximate universality remains hard for any fixed polynomially computable epsilon.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 13