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

Abstract

top
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.

How to cite

top

Carton, 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
  1. J. Berstel, Transductions and context-free languages. B.G. Teubner (1979).  
  2. A. Bertoni and P. Massazza, On the inclusion problem for finitely ambiguous rational trace languages. RAIRO: Inform. Théor. Appl.32 (1998) 79–98.  
  3. S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press (1974).  
  4. S. Eilenberg, C.C. Elgot and J.C. Shepherdson, Sets recognized by n-tape automata. J. Algebra3 (1969) 447–464.  
  5. S. Eilenberg and M.-P. Schützenbeger, Rational sets in commutative monoids. J. Algebra13 (1969) 173–191.  
  6. C.C. Elgot and J.E. Mezei, On Relations Defined by Finite Automata. IBM J.10 (1965) 47–68.  
  7. P.C. Fischer and A.L. Rosenberg, Multitape one-way nonwriting automata. J. Comput. Syst. Sci.2 (1968) 88–101.  
  8. S. Ginsburg and E.H. Spanier, Semigroups, Presburger formulas, and languages. Pacific J. Math.16 (1966) 285–296.  
  9. E. Grädel, Subclasses of Presburger arithmetic and the polynomial hierarchy. Theoret. Comput. Sci.56 (1989) 281–301.  
  10. 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.  
  11. 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.  
  12. M. Rabin and D. Scott, Finite automata and their decision problems. IBM J. Res. Develop (1959) 125–144.  
  13. J. Sakarovitch, Éléments de théorie des automates. Vuibert Informatique (2003).  
  14. R.E. Stearns, A regularity test for pushdown machines. Inform. Control11 (1967) 323–340.  
  15. L.G. Valiant, Regularity and related problems for deterministic pushdown automata. Inform. Control22 (1975) 1–10.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.