Semilinear Sets and Counter Machines : a Brief Survey

• Autorzy: Ibarra O. H. , Seki S.

Identyfikatory

DOI

10.3233/FI-2015-1198

• Języki publikacji: EN

Abstrakty

EN

Semilinear sets are one of the most important concepts in theoretical computer science, as illustrated by the fact that the set of nonnegative integer solutions to any system of Diophantine equations is semilinear. Parikh’s theorem enables us to represent any semilinear set as a pushdown automaton (PDA).We summarize recent results on the descriptional complexity of conversions among different representations of a semilinear set: as a vector set (conventional), a finite automaton (FA), a PDA, etc.. We also discuss semilinearity-preserving operations like union, intersection, and complement. We use Parikh’s theorem to enlarge the class of finite-state machines that can represent semilinear sets. In particular, we give a simpler proof of a known result that characterizes semilinear sets in terms of machines with reversal-bounded counters. We then investigate the power of such a machine with only one counter in the context of a long-standing conjecture about repetition on words.

Słowa kluczowe

EN

semilinear set; reversal bounded counter machine; Parikh’s theorem; linear Diophantine equations; descriptional complexity; closure property; decidable; undecidable

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 138, nr 1/2
• Strony: 61--76
• Opis fizyczny: Bibliogr. 42 poz.

Twórcy

autor

Ibarra O. H.

• Department of Computer Science, University of California Santa Barbara, CA 93106, USA

autor

Seki S.

• Helsinki Institute for Information Technology (HIIT) Department of Information and Computer Science, Aalto University P. O. Box 15400, FI-00076, Aalto, Finland

Bibliografia

• [1] Aceto, L., ´Esik, Z., Ing´olfsd´ottir, A.: A Fully Equational Proof of Parikh’s Theorem, RAIRO-Theor. Inf. Appl., 36, 2002, 129–153.
• [2] Baker, B. S., Book, R. V.: Reversal-Bounded Multipushdown Machines, J. Comput. Syst. Sci., 8, 1974, 315–332.
• [3] Berstel, J.: Transductions and Context-Free Languages, B. G. Teubner, 1979.
• [4] Böhm, S., Cöller, S., Jancar, P.: Equivalence of Deterministic One-Counter Automata is NL-Complete, Proc. STOC 2013, ACM, 2013.
• [5] Chiniforooshan, E., Daley, M., Ibarra, O. H., Kari, L., Seki, S.: One-Reversal Counter Machines with Multihead Automata: Revisited, Proc. SOFSEM 2011, 6543, Springer, 2011.
• [6] Choffrut, C., Malcher, A., Mereghetti, C., Palano, B.: First-Order Logics: Some Characterizations and Closure Properties, Acta. Inform., 49(4), 2012, 225–248.
• [7] Dang, Z., Ibarra, O. H., Sun, Z.-W.: On Two-Way Nondeterministic Finite Automata with One Reversal-Bounded Counter, Theor. Comput. Sci., 330(1), 2005, 59–79.
• [8] Dömösi, P., Horváth, S., Ito, M., Kászonyi, L., Katsura, M.: Formal Languages Consisting of Primitive Words, Proc. FCT 1993, 710, Springer, 1993.
• [9] Engelfriet, J., Hoogeboom, H. J.: Finitary Compositions of Two-Way Finite-State Transductions, Fund. Inform., 80(1-3), 2008, 111–123.
• [10] Esparza, J.: Petri Nets, Commutative Context-Free Grammars, and Basic Parallel Processes, Fund. Inform., 31(1), 1997, 13–25.
• [11] Esparza, J., Ganty, P., Kiefer, S., Luttenberger, M.: Parikh’s Theorem: A Simple and Direct Automaton Construction, Inform. Process. Lett., 111, 2011, 614–619.
• [12] Filiot, E., Raskin, J.-F., Reynier, P.-A., Servais, F., Talbot, J.-M.: Properties of Visibly Pushdown Transducers, Proc. MFCS 2010, 6281, Springer, 2010.
• [13] Fine, N. J., Wilf, H. S.: Uniqueness Theorems for Periodic Functions, Proc. Amer. Math. Soc., 16, 1965, 109–114.
• [14] Ginsburg, S., Rice, H. G.: Two Families of Languages Related to ALGOL, J. ACM, 9, 1962, 350–371.
• [15] Ginsburg, S., Spanier, E. H.: Bounded ALGOL-like Languages, T. Am. Math. Soc., 113, 1964, 333–368.
• [16] Greibach, S. A.: An Infinite Hierarchy of Context-Free Languages, J. ACM, 16(1), 1969, 91–106.
• [17] Gurari, E. M., Ibarra, O. H.: The Complexity of Decision Problems for Finite-Turn Multicounter Machines, J. Comput. Syst. Sci., 22, 1981, 220–229.
• [18] Gurari, E. M., Ibarra, O. H.: Two-Way Counter Machines and Diophantine Equations, J. ACM, 29(3), 1982, 863–873.
• [19] Hague, M., Lin, A. W.: Model Checking Recursive Programs with Numeric Data Types, Proc. CAV 2011, 6806, Springer, 2011.
• [20] Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.
• [21] Huynh, T.-D.: The Complexity of Semilinear Sets, Proc. ICALP 1980, 85, Springer, 1980.
• [22] Ibarra, O. H.: Reversal-Bounded Multicounter Machines and Their Decision Problems, J. ACM, 25, 1978, 116–133.
• [23] Ibarra, O. H., Dang, Z.: On Two-Way FA with Monotonic Counters and Quadratic Diophantine Equations, Theor. Comput. Sci., 312(2-3), 2004, 359–378.
• [24] Ibarra, O. H., Dang, Z.: On the Solvability of a Class of Diophantine Equations and Applications, Theor. Comput. Sci., 352(1-3), 2006, 342–346.
• [25] Ibarra, O. H., Dang, Z., Yang, L.: On CounterMachines, Reachability Problems, and Diophantine Equations, Int. J. Found. Comput. S., 19(4), 2008, 919–934.
• [26] Ibarra, O. H., Jiang, T., Trˆan, N. Q., Wang, H.: New Decidability Results Concerning Two-Way Counter Machines, SIAM J. Comput., 24(1), 1995, 123–137.
• [27] Ibarra, O. H., Ravikumar, B.: On the Parikh Membership Problem for FAs, PDAs, and CMs, Proc. LATA 2014, 8370, Springer, 2014.
• [28] Ibarra, O. H., Seki, S.: Characterizations of Bounded Semilinear Languages by One-Way and Two-Way Deterministic Machines, Int. J. Found. Comput. S., 23(6), 2012, 1291–1305.
• [29] Ibarra, O. H., Su, J.: A Technique for Proving Decidability of Containment and Equivalence of Linear Constraint Queries, J. Comput. Syst. Sci., 59(1), 1999, 1–28.
• [30] Ibarra, O. H., Yen, H.-C.: On the Containment and Equivalence Problems for Two-Way Transducers, Theor. Comput. Sci., 429, 2012, 155–163.
• [31] Ito, M.: Personal communication.
• [32] Kopczyński, E., To, A. W.: Parikh Images of Grammars: Complexity and Applications, Proc. LICS 2010, 2010.
• [33] Lavado, G. J., Pighizzini, G., Seki, S.: Operational State Complexity under Parikh Equivalence, Submitted.
• [34] Lavado, G. J., Pighizzini, G., Seki, S.: Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent One-Way and Two-Way Deterministic Automata, Inform. Comput., 228-229, 2013, 1–15.
• [35] Liu, L.,Weiner, P.: Finite-Reversal PushdownAutomata and Semi-linear Sets, Proceedings of the 2nd Annual Princeton Conference on Information Sciences and Systems, 1968.
• [36] Minsky,M. L.: Computation: Finite and Infinite Machines, Prentice-Hall, 1967.
• [37] Ogden,W. F.: A Helpful Result for Proving Inherent Ambiguity, Math. Syst. Theory, 2(3), 1968, 191–194.
• [38] Parikh, R. J.: On Context-Free Languages, J. ACM, 13, 1966, 570–581.
• [39] Pighizzini, G., Shallit, J., Wang, M.-W.: Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds, J. Comput. Syst. Sci., 65, 2002, 393–414.
• [40] Rozenberg, G., Salomaa, A., Eds.: Handbook of Formal Languages, Vol. 1: Word, Language, Grammar, Springer, 1997.
• [41] Schroeppel, R.: A Two Counter Machine Cannot Calculate 2N, Technical report, M.I.T. A.I. Laboratory, 1972, Artificial Intelligence Memo #257.
• [42] To, A. W.: Parikh Images of Regular Languages: Complexity and Applications, ArXiv: 1002.1464.