|
| << vorige |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 25 van 25 gevonden artikelen
| Titel: |
Undecidability in ω-Regular Languages |
| Auteur: |
Halava, Vesa Harju, Tero Karhumäki, Juhani |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 73 (2006) nr. 1-2 pagina's 119-125 |
| Jaar: |
2006-08-28 |
| Inhoud: |
In the infinite Post Correspondence Probleman instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists an infinite word α such that h(α)=g(α). In the general case this problemwas shown to be undecidable by K. Ruohonen (1985). Recently, it was proved that the infinite PCP is undecidable already when the domain alphabet of the morphisms consists of at least 9 letters. Here we show that the problem is undecidable for instances where the morphisms have a domain of 6 letters, when we restrict to solutions of ω-languages of the form R^{ω} where R is a given regular language. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 25 van 25 gevonden artikelen
| << vorige |