# Decision problems among the main subfamilies of rational relations

Olivier Carton; Christian Choffrut; Serge Grigorieff

RAIRO - Theoretical Informatics and Applications (2006)

- Volume: 40, Issue: 2, page 255-275
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topCarton, Olivier, Choffrut, Christian, and Grigorieff, Serge. "Decision problems among the main subfamilies of rational relations." RAIRO - Theoretical Informatics and Applications 40.2 (2006): 255-275. <http://eudml.org/doc/249706>.

@article{Carton2006,

abstract = {
We consider the four families of recognizable, synchronous,
deterministic rational and rational subsets of a direct product
of free monoids.
They form a strict hierarchy and we investigate the following
decision problem: given a relation in one of the families,
does it belong to a smaller family?
We settle the problem entirely when all monoids have a unique
generator and fill some gaps in the general case.
In particular, adapting a proof of Stearns, we show that it is recursively decidable
whether or not a deterministic subset of an arbitrary
number of free monoids is recognizable.
Also we exhibit a single exponential algorithm
for determining if a synchronous relation is recognizable.
},

author = {Carton, Olivier, Choffrut, Christian, Grigorieff, Serge},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Multitape automata; Presburger arithmetics; decision problems.; multitape automata; decision problems},

language = {eng},

month = {7},

number = {2},

pages = {255-275},

publisher = {EDP Sciences},

title = {Decision problems among the main subfamilies of rational relations},

url = {http://eudml.org/doc/249706},

volume = {40},

year = {2006},

}

TY - JOUR

AU - Carton, Olivier

AU - Choffrut, Christian

AU - Grigorieff, Serge

TI - Decision problems among the main subfamilies of rational relations

JO - RAIRO - Theoretical Informatics and Applications

DA - 2006/7//

PB - EDP Sciences

VL - 40

IS - 2

SP - 255

EP - 275

AB -
We consider the four families of recognizable, synchronous,
deterministic rational and rational subsets of a direct product
of free monoids.
They form a strict hierarchy and we investigate the following
decision problem: given a relation in one of the families,
does it belong to a smaller family?
We settle the problem entirely when all monoids have a unique
generator and fill some gaps in the general case.
In particular, adapting a proof of Stearns, we show that it is recursively decidable
whether or not a deterministic subset of an arbitrary
number of free monoids is recognizable.
Also we exhibit a single exponential algorithm
for determining if a synchronous relation is recognizable.

LA - eng

KW - Multitape automata; Presburger arithmetics; decision problems.; multitape automata; decision problems

UR - http://eudml.org/doc/249706

ER -

## References

top- J. Berstel, Transductions and context-free languages. B.G. Teubner (1979).
- A. Bertoni and P. Massazza, On the inclusion problem for finitely ambiguous rational trace languages. RAIRO: Inform. Théor. Appl.32 (1998) 79–98.
- S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press (1974).
- S. Eilenberg, C.C. Elgot and J.C. Shepherdson, Sets recognized by n-tape automata. J. Algebra3 (1969) 447–464.
- S. Eilenberg and M.-P. Schützenbeger, Rational sets in commutative monoids. J. Algebra13 (1969) 173–191.
- C.C. Elgot and J.E. Mezei, On Relations Defined by Finite Automata. IBM J.10 (1965) 47–68.
- P.C. Fischer and A.L. Rosenberg, Multitape one-way nonwriting automata. J. Comput. Syst. Sci.2 (1968) 88–101.
- S. Ginsburg and E.H. Spanier, Semigroups, Presburger formulas, and languages. Pacific J. Math.16 (1966) 285–296.
- E. Grädel, Subclasses of Presburger arithmetic and the polynomial hierarchy. Theoret. Comput. Sci.56 (1989) 281–301.
- O.H. Ibarra, The unsolvability of the equivalence problem for ε-free ngsm's with unary input (output) alphabets and application. SIAM J. Comput.7 (1978) 520–532.
- L.P. Lisovik, The identity problem for regular events over the direct product of free and cyclic semigroups. Dok. Akad. Nauk Ukrainskoj RSR Ser. A.6 (1979) 410–413.
- M. Rabin and D. Scott, Finite automata and their decision problems. IBM J. Res. Develop (1959) 125–144.
- J. Sakarovitch, Éléments de théorie des automates. Vuibert Informatique (2003).
- R.E. Stearns, A regularity test for pushdown machines. Inform. Control11 (1967) 323–340.
- L.G. Valiant, Regularity and related problems for deterministic pushdown automata. Inform. Control22 (1975) 1–10.

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.