Publication
The word problem for omega-terms over DA
| dc.contributor.author | Moura, Ana | |
| dc.date.accessioned | 2018-03-21T14:23:19Z | |
| dc.date.available | 2018-03-21T14:23:19Z | |
| dc.date.issued | 2011 | |
| dc.description.abstract | In this paper, we solve the word problem for ω-terms over DA. We extend to DA the ideas used by Almeida and Zeitoun to solve the analogous problem for the pseudovariety R applying also a representation by automata of implicit operations on DA, which was recently obtained by the author. Considering certain types of factors of an implicit operation on DA, we can prove that a pseudoword on DA is an ω-term if and only if the associated minimal DA- automaton is finite. Finally, we complete the result by effectively computing in polynomial time the minimal DA-automaton associated to an ω-term. | pt_PT |
| dc.description.version | info:eu-repo/semantics/publishedVersion | pt_PT |
| dc.identifier.doi | 10.1016/j.tcs.2011.08.003 | pt_PT |
| dc.identifier.uri | http://hdl.handle.net/10400.22/11163 | |
| dc.language.iso | eng | pt_PT |
| dc.peerreviewed | yes | pt_PT |
| dc.publisher | Elsevier | pt_PT |
| dc.relation.ispartofseries | Theoretical Computer Science;Volume 412, Issue 46 | |
| dc.relation.publisherversion | https://www.sciencedirect.com/science/article/pii/S0304397511006645 | pt_PT |
| dc.subject | Finite monoid | pt_PT |
| dc.subject | Pseudovariety | pt_PT |
| dc.subject | Word problem | pt_PT |
| dc.subject | Pseudoword | pt_PT |
| dc.subject | Omega-term | pt_PT |
| dc.subject | Aperiodic | pt_PT |
| dc.subject | Regular D-class | pt_PT |
| dc.title | The word problem for omega-terms over DA | pt_PT |
| dc.type | journal article | |
| dspace.entity.type | Publication | |
| oaire.citation.endPage | 6569 | pt_PT |
| oaire.citation.startPage | 6556 | pt_PT |
| oaire.citation.title | Theoretical Computer Science | pt_PT |
| oaire.citation.volume | 412 | pt_PT |
| rcaap.rights | openAccess | pt_PT |
| rcaap.type | article | pt_PT |