|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 3 van 13 gevonden artikelen
| Titel: |
Computational Universality in One-variable Language Equations |
| Auteur: |
Okhotin, Alexander |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 74 (2006) nr. 4 pagina's 563-578 |
| Jaar: |
2006-12-12 |
| Inhoud: |
It has recently been shown that several computational models, such as trellis automata, recursive functions and Turing machines, admit characterization by resolved systems of language equations with different sets of language-theoretic operations. This paper investigates how simple the systems of equations from the computationally universal types could be while still retaining their universality. It is proved that the universality and the associated hardness of decision problems begins at one-variable equations. Additionally, it is shown that language equations with added quotient with regular languages can specify every set representable in first-order Peano arithmetic. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 3 van 13 gevonden artikelen
| << vorige | volgende >> |