Go to:
Logótipo
Você está em: Start > Publications > View > Approximate NFA universality and related problems motivated by information theory & nbsp;
Map of Premises
Principal
Publication

Approximate NFA universality and related problems motivated by information theory & nbsp;

Title
Approximate NFA universality and related problems motivated by information theory & nbsp;
Type
Article in International Scientific Journal
Year
2023
Authors
Konstantinidis, S
(Author)
Other
The person does not belong to the institution. The person does not belong to the institution. The person does not belong to the institution. Without AUTHENTICUS Without ORCID
Mastnak, M
(Author)
Other
The person does not belong to the institution. The person does not belong to the institution. The person does not belong to the institution. Without AUTHENTICUS Without ORCID
Nelma Moreira
(Author)
FCUP
View Personal Page You do not have permissions to view the institutional email. Search for Participant Publications View Authenticus page View ORCID page
Rogério Reis
(Author)
FCUP
View Personal Page You do not have permissions to view the institutional email. Search for Participant Publications View Authenticus page View ORCID page
Journal
Vol. 972
ISSN: 0304-3975
Publisher: Elsevier
Other information
Authenticus ID: P-00Y-RXY
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;.& COPY; 2023 Elsevier B.V. All rights reserved.
Language: English
Type (Professor's evaluation): Scientific
No. of pages: 16
Documents
We could not find any documents associated to the publication.
Related Publications

Of the same authors

Approximate NFA Universality Motivated by Information Theory (2022)
Article in International Conference Proceedings Book
Konstantinidis, S; Mastnak, M; Nelma Moreira; Rogério Reis

Of the same journal

Weak linearization of the lambda calculus (2005)
Article in International Scientific Journal
Alves, S; Florido, M
Turing machines and bimachines (2008)
Article in International Scientific Journal
John Rhodes; Pedro V. Silva
Turing machines and bimachines (2008)
Article in International Scientific Journal
Rhodes, J; Pedro V. Silva
The k-word problem over DRH (2017)
Article in International Scientific Journal
Célia Borlido
The homomorphism problem for trace monoids (2003)
Article in International Scientific Journal
Pedro V. Silva

See all (37)

Recommend this page Top
Copyright 1996-2025 © Faculdade de Medicina Dentária da Universidade do Porto  I Terms and Conditions  I Acessibility  I Index A-Z
Page created on: 2025-07-10 at 00:38:43 | Privacy Policy | Personal Data Protection Policy | Whistleblowing | Electronic Yellow Book