Geodesic
Decision Problems for Subclasses of Rational Relations over Finite and Infinite Words
Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 3.

Voir la notice de l'article provenant de la source Episciences

We consider decision problems for relations over finite and infinite words defined by finite automata. We prove that the equivalence problem for binary deterministic rational relations over infinite words is undecidable in contrast to the case of finite words, where the problem is decidable. Furthermore, we show that it is decidable in doubly exponential time for an automatic relation over infinite words whether it is a recognizable relation. We also revisit this problem in the context of finite words and improve the complexity of the decision procedure to single exponential time. The procedure is based on a polynomial time regularity test for deterministic visibly pushdown automata, which is a result of independent interest. 
@article{DMTCS_2019_21_3_a4,
     author = {L\"oding, Christof and Spinrath, Christopher},
     title = {Decision {Problems} for {Subclasses} of {Rational} {Relations} over {Finite} and {Infinite} {Words}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2019},
     doi = {10.23638/DMTCS-21-3-4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-4/}
}
TY  - JOUR
AU  - Löding, Christof
AU  - Spinrath, Christopher
TI  - Decision Problems for Subclasses of Rational Relations over Finite and Infinite Words
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-4/
DO  - 10.23638/DMTCS-21-3-4
LA  - en
ID  - DMTCS_2019_21_3_a4
ER  - 
%0 Journal Article
%A Löding, Christof
%A Spinrath, Christopher
%T Decision Problems for Subclasses of Rational Relations over Finite and Infinite Words
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-4/
%R 10.23638/DMTCS-21-3-4
%G en
%F DMTCS_2019_21_3_a4
Löding, Christof; Spinrath, Christopher. Decision Problems for Subclasses of Rational Relations over Finite and Infinite Words. Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 3. doi : 10.23638/DMTCS-21-3-4. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-4/

Cité par Sources :