Christof Löding ; Christopher Spinrath - Decision Problems for Subclasses of Rational Relations over Finite and Infinite Words

dmtcs:4393 - Discrete Mathematics & Theoretical Computer Science, January 31, 2019, Vol. 21 no. 3 - https://doi.org/10.23638/DMTCS-21-3-4
Decision Problems for Subclasses of Rational Relations over Finite and Infinite WordsArticle

Authors: Christof Löding ; Christopher Spinrath

    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.


    Volume: Vol. 21 no. 3
    Section: Automata, Logic and Semantics
    Published on: January 31, 2019
    Accepted on: January 17, 2019
    Submitted on: March 20, 2018
    Keywords: Computer Science - Formal Languages and Automata Theory,F.4.3

    Consultation statistics

    This page has been seen 937 times.
    This article's PDF has been downloaded 555 times.