2015/09/24 by Christian Wurm
Computer Science · #cs.FL #cs.CC
paper · pdf · doi:10.4204/eptcs.193.5
published as EPTCS 193, 2015, pp. 58-72 · In Proceedings GandALF 2015, arXiv:1509.06858
arxiv created 2015/09/24 · arxiv updated 2015/09/25
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.