In this paper we continue the research on usefulness of information examining the effect of supplementary information on the complexity of solving a problem (see Rovan and Sádovský [7] for an overview). We use deterministic finite automata for a formal setting. Given a problem (a regular language) LprobLprob we measure the complexity of its solution – a DFA AprobAprob such that Lprob=L(Aprob)Lprob=L(Aprob) – using the state complexity. A supplementary information (advice) LadvLadv given by AadvAadv is useful if a simpler problem LnewLnew given by AnewAnew exists such that Lprob=Lnew∩LadvLprob=Lnew∩Ladv and both LnewLnew and LadvLadv are simpler than LprobLprob. This is formalized via the notion of decomposability of finite automata (see [1] for DFA case and [7] for NFA case). We address the problem of decomposability of unary regular languages and give a characterization of λλ-cyclic languages upon deterministic decomposability

Usefulness of Information and Unary Languages / G. Pighizzini, B. Rovan, Š. Sádovský (LECTURE NOTES IN COMPUTER SCIENCE). - In: Language and Automata Theory and Applications / [a cura di] A. Leporati, C. Martín-Vide, D. Shapira, C. Zandron. - [s.l] : Springer, 2021. - ISBN 9783030681944. - pp. 131-142 (( Intervento presentato al 15. convegno Language and Automata Theory and Applications tenutosi a Milano nel 2021 [10.1007/978-3-030-68195-1_11].

Usefulness of Information and Unary Languages

G. Pighizzini;
2021

Abstract

In this paper we continue the research on usefulness of information examining the effect of supplementary information on the complexity of solving a problem (see Rovan and Sádovský [7] for an overview). We use deterministic finite automata for a formal setting. Given a problem (a regular language) LprobLprob we measure the complexity of its solution – a DFA AprobAprob such that Lprob=L(Aprob)Lprob=L(Aprob) – using the state complexity. A supplementary information (advice) LadvLadv given by AadvAadv is useful if a simpler problem LnewLnew given by AnewAnew exists such that Lprob=Lnew∩LadvLprob=Lnew∩Ladv and both LnewLnew and LadvLadv are simpler than LprobLprob. This is formalized via the notion of decomposability of finite automata (see [1] for DFA case and [7] for NFA case). We address the problem of decomposability of unary regular languages and give a characterization of λλ-cyclic languages upon deterministic decomposability
Settore INF/01 - Informatica
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
main.pdf

accesso riservato

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 308.15 kB
Formato Adobe PDF
308.15 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pighizzini2021_Chapter_UsefulnessOfInformationAndUnar.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 354.97 kB
Formato Adobe PDF
354.97 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/817188
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact