Deciding Whether or Not a Synchronous Relation is Regular Prefix

• Autorzy: Choffrut C.

Identyfikatory

DOI

10.3233/FI-2014-1053

• Języki publikacji: EN

Abstrakty

EN

Eilenberg and al. introduced and studied in the late sixties the family of n-ary relations over the free monoid recognized by finite n-tape automata where the where the n reading heads tapes move simultaneously from left to right. We call these relations synchronous. In the eighties Angluin and Hoover and then L¨auchli and Savioz introduced a proper subfamily which the first authors called regular prefix. Our main result shows that given a synchronous relation it is decidable whether or not it is regular prefix. Incidentallywe also show that the family of regular prefix relations is uniformizable in the sense that all such relations contain a partial function with the same domain whose graph is a regular prefix relation.

Słowa kluczowe

EN

monoids; finite state machine; graph theory; regular graphs; mathematical analysis

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 132, nr 4
• Strony: 439--459
• Opis fizyczny: Bibliogr. 12 poz., rys., tab.

Twórcy

autor

Choffrut C.

• L.I.A.F.A., Universite Paris 7, France

Bibliografia

• [1] Dana Angluin and Douglas N. Hoover. Regular prefix relations. Mathematical Systems Theory, 17(3):167–191, 1984.
• [2] Michael Benedikt, Leonid Libkin, Thomas Schwentick, and Luc Segoufin. Definable relations and first-order query languages over strings. J. ACM, 50(5):694–751, 2003.
• [3] Olivier Carton, Christian Choffrut, and Serge Grigorieff. Decision problems among the main subfamilies of rational relations. ITA, 40(2):255–275, 2006.
• [4] Christian Choffrut and Serge Grigorieff. The theory of rational relations on transfinite strings. In Words, Languages and Combinatorics III (Kyoto, March 2000), volume 12, pages 103–151.World Scientific, 2004.
• [5] Samuel Eilenberg. Automata, Languages and Machines, volume A. Academic Press, 1974.
• [6] Samuel Eilenberg, Calvin C. Elgot, and J. C. Shepherdson. Sets recognized by n-tape automata. J. Algebra, 3:447–464, 1969.
• [7] Calvin C. Elgot and Jorge E. Mezei. On Relations Defined by Finite Automata. IBM Journal, 10:47–68, 1965.
• [8] Patrick C. Fischer and Arnold L. Rosenberg. Multitape one-way nonwriting automata. J. Comput. System Sci., 2:88–101, 1968.
• [9] Christiane Frougny and Jacques Sakarovitch. Synchronized rational relations of finite and infinite words. Theoretical Computer Science, 108:45–82, 1993.
• [10] Hans Laüchli and Christian Savioz. Monadic second order definable relations on the binary tree. J. Symb. Log., 52(1), 1987.
• [11] Richard E. Stearns. A regularity test for pushdown machines. Informationa and Control, 11:323–340, 1967.
• [12] Wolfgang Thomas. Infinite trees and automation-definable relations over omega-words. Theor. Comput. Sci., 103(1):143–159, 1992.