Synchronous Subsequentiality and Approximations to Undecidable Problems

Christian Wurm
(Universität Düsseldorf)

We introduce the class of synchronous subsequential relations, a subclass of the synchronous relations which embodies some properties of subsequential relations. If we take relations of this class as forming the possible transitions of an infinite automaton, then most decision problems (apart from membership) still remain undecidable (as they are for synchronous and subsequential rational relations), but on the positive side, they can be approximated in a meaningful way we make precise in this paper. This might make the class useful for some applications, and might serve to establish an intermediate position in the trade-off between issues of expressivity and (un)decidability.

In Javier Esparza and Enrico Tronci: Proceedings Sixth International Symposium on Games, Automata, Logics and Formal Verification (GandALF 2015), Genoa, Italy, 21-22nd September 2015, Electronic Proceedings in Theoretical Computer Science 193, pp. 58–72.
Published: 23rd September 2015.

ArXived at: http://dx.doi.org/10.4204/EPTCS.193.5 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org