On fixed points of rational transductions (Q1637233)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 6882163
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On fixed points of rational transductions |
scientific article; zbMATH DE number 6882163 |
Statements
On fixed points of rational transductions (English)
0 references
7 June 2018
0 references
In this short paper, the authors prove that the fixed point problem for injective rational functions is undecidable. A function is called rational, if it can be computed by a transducer (an automaton with outputs). For this, the authors use the undecidability of the Post corresponding problem for injective morphisms and some characterizations of rational transduction functions by Nivat and Latteux-Leguy. As a corollary, it is shown that the fixed point problem is undecidable for injective computable functions (on natural numbers).
0 references
fixed points
0 references
rational transductions
0 references
post correspondence problem
0 references
injective PCP
0 references
decidability
0 references
0.8420541286468506
0 references
0.7885589003562927
0 references
0.7624360918998718
0 references
