An Example of Π30-complete Infinitary Rational Relation
We give in this paper an example of infinitary rational relation, accepted by a 2-tape Buchi automaton, which is Π30-complete in the Borel hierarchy. Moreover the example of infinitary rational relation given in this paper has a very simple structure and can be easily described by its sections.
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Vladimir Andrunachievici Institute of Mathematics and Computer Science
2007-04-01
|
| Series: | Computer Science Journal of Moldova |
| Subjects: | |
| Online Access: | http://www.math.md/files/csjm/v15-n1/v15-n1-(pp3-21).pdf |
| _version_ | 1811278786807726080 |
|---|---|
| author | Olivier Finkel |
| author_facet | Olivier Finkel |
| author_sort | Olivier Finkel |
| collection | DOAJ |
| description | We give in this paper an example of infinitary rational relation, accepted by a 2-tape Buchi automaton, which is Π30-complete in the Borel hierarchy. Moreover the example of infinitary rational relation given in this paper has a very simple structure and can be easily described by its sections. |
| first_indexed | 2024-04-13T00:42:02Z |
| format | Article |
| id | doaj.art-5a38c78fb4cc4e86b6bdbe00e491f793 |
| institution | Directory Open Access Journal |
| issn | 1561-4042 |
| language | English |
| last_indexed | 2024-04-13T00:42:02Z |
| publishDate | 2007-04-01 |
| publisher | Vladimir Andrunachievici Institute of Mathematics and Computer Science |
| record_format | Article |
| series | Computer Science Journal of Moldova |
| spelling | doaj.art-5a38c78fb4cc4e86b6bdbe00e491f7932022-12-22T03:10:07ZengVladimir Andrunachievici Institute of Mathematics and Computer ScienceComputer Science Journal of Moldova1561-40422007-04-01151(43)321An Example of Π30-complete Infinitary Rational RelationOlivier Finkel0Equipe Modeles de Calcul et Complexite Laboratoire de l'Informatique du Parallelisme CNRS et Ecole Normale Superieure de Lyon 46, Allee d'Italie 69364 Lyon Cedex 07, FranceWe give in this paper an example of infinitary rational relation, accepted by a 2-tape Buchi automaton, which is Π30-complete in the Borel hierarchy. Moreover the example of infinitary rational relation given in this paper has a very simple structure and can be easily described by its sections.http://www.math.md/files/csjm/v15-n1/v15-n1-(pp3-21).pdfInfinitary rational relationstopological propertiesBorel hierarchyΠ30-complete set |
| spellingShingle | Olivier Finkel An Example of Π30-complete Infinitary Rational Relation Computer Science Journal of Moldova Infinitary rational relations topological properties Borel hierarchy Π30-complete set |
| title | An Example of Π30-complete Infinitary Rational Relation |
| title_full | An Example of Π30-complete Infinitary Rational Relation |
| title_fullStr | An Example of Π30-complete Infinitary Rational Relation |
| title_full_unstemmed | An Example of Π30-complete Infinitary Rational Relation |
| title_short | An Example of Π30-complete Infinitary Rational Relation |
| title_sort | example of π30 complete infinitary rational relation |
| topic | Infinitary rational relations topological properties Borel hierarchy Π30-complete set |
| url | http://www.math.md/files/csjm/v15-n1/v15-n1-(pp3-21).pdf |
| work_keys_str_mv | AT olivierfinkel anexampleofp30completeinfinitaryrationalrelation AT olivierfinkel exampleofp30completeinfinitaryrationalrelation |