On universality of regular realizability problems
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916430144864256 |
|---|---|
| author | Rubtsov, Alexander Vyalyi, Michael |
| author_facet | Rubtsov, Alexander Vyalyi, Michael |
| contents | We prove the universality of the regular realizability problems for several classes of filters. The filters are encodings of finite relations on the set of non-negative integers in the format proposed by P. Wolf and H. Fernau. The universality has proven up to disjunctive truth table polynomial reductions for unary relations and polynomial space reductions for invariant binary relations. Stronger reductions correspond to the results of P. Wolf and H. Fernau about decidability of regular realizability problems for many graph-theoretic properties. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_15381 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On universality of regular realizability problems Rubtsov, Alexander Vyalyi, Michael Formal Languages and Automata Theory 68Q45 F.4.3 We prove the universality of the regular realizability problems for several classes of filters. The filters are encodings of finite relations on the set of non-negative integers in the format proposed by P. Wolf and H. Fernau. The universality has proven up to disjunctive truth table polynomial reductions for unary relations and polynomial space reductions for invariant binary relations. Stronger reductions correspond to the results of P. Wolf and H. Fernau about decidability of regular realizability problems for many graph-theoretic properties. |
| title | On universality of regular realizability problems |
| topic | Formal Languages and Automata Theory 68Q45 F.4.3 |
| url | https://arxiv.org/abs/2311.15381 |