Decision problems for subclasses of rational relations over finite and infinite words

DOI10.1007/978-3-662-55751-8_27MaRDI QIDQ1679989zbMATH OpenOpenAlexFDO

Authors Christof Löding, Christopher Spinrath

Publication date 22 November 2017

Full work available at URL https://arxiv.org/abs/1803.06140

zbMATH Keywords

visibly pushdown automatarational relations\(\omega\)-automatafinite transducersautomatic relations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 7058469
• The decision problem for some logics for finite words on infinite alphabets
• Decision problems among the main subfamilies of rational relations
• Decision Problems and Applications of Rational Sets of Regular Languages
• Decision problems for equational theories of relation algebras
• scientific article; zbMATH DE number 638616
• scientific article; zbMATH DE number 887303
• A class of rational relations generalising the subword order
• Some decisional problems on rational relations
• Decision Problems for Finite Automata over Infinite Algebraic Structures

Cited in

(12)

• Some decisional problems on rational relations
• Rational equivalence relations
• scientific article; zbMATH DE number 3982545 (Why is no real title available?)
• Synchronized rational relations of finite and infinite words
• A class of rational relations generalising the subword order
• Decision Problems and Applications of Rational Sets of Regular Languages
• Modelization of deterministic rational relations
• scientific article; zbMATH DE number 3911744 (Why is no real title available?)
• A note on the decidability of subword inequalities
• Decision problems among the main subfamilies of rational relations
• scientific article; zbMATH DE number 7058469 (Why is no real title available?)
• scientific article; zbMATH DE number 7561596 (Why is no real title available?)

This page was built for publication: Decision problems for subclasses of rational relations over finite and infinite words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1679989)