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

DOI10.1007/978-3-662-55751-8_27zbMATH Open1416.68105arXiv1803.06140OpenAlexW2963249196MaRDI QIDQ1679989FDOQ1679989

Authors: Christof Löding, Christopher Spinrath 

Publication date: 22 November 2017

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.

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

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

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)

Cited In (12)

• Some decisional problems on rational relations
• Title not available (Why is that?)
• Rational equivalence relations
• A class of rational relations generalising the subword order
• Synchronized rational relations of finite and infinite words
• Decision Problems and Applications of Rational Sets of Regular Languages
• Modelization of deterministic rational relations
• Title not available (Why is that?)
• A note on the decidability of subword inequalities
• Decision problems among the main subfamilies of rational relations
• Title not available (Why is that?)
• Title not available (Why is that?)

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)