nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Semilinearity of Families of Languages

verfasst von : Oscar H. Ibarra, Ian McQuillan

Erschienen in: Implementation and Application of Automata

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Techniques are developed for creating new and general language families of only semilinear languages, and for showing families only contain semilinear languages. It is shown that for language families \(\mathcal{L}\) that are semilinear full trios, the smallest full AFL containing the languages obtained by intersecting languages in \(\mathcal{L}\) with languages in \(\mathsf{NCM}\) (where \(\mathsf{NCM}\) is the family of languages accepted by \(\textsf {NFA}\)s augmented with reversal-bounded counters), is also semilinear. If these closure properties are effective, this also immediately implies decidability of membership, emptiness, and infiniteness for these general families. From the general techniques, new grammar systems are given that are extensions of well-known families of semilinear full trios, whereby it is implied that these extensions must only describe semilinear languages. This also implies positive decidability properties for the new systems. Some characterizations of the new families are also given.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel The Ranges of Accepting State Complexities of Languages Resulting From Some Operations

Nächstes Kapitel The Exact Complexity of Star-Complement-Star

A worktape is finite-crossing if there is a bound on the number of times the boundary of all neighboring cells on the worktape are crossed.

Aho, A.V.: Indexed grammars–an extension of context-free grammars. J. ACM 15(4), 647–671 (1968)MathSciNetCrossRef

Breveglieri, L., Cherubini, A., Citrini, C., Reghizzi, S.: Multi-push-down languages and grammars. Int. J. Found. Comput. Sci. 7(3), 253–291 (1996)CrossRef

D’Alessandro, F., Ibarra, O.H., McQuillan, I.: On finite-index indexed grammars and their restrictions. In: Drewes, F., Martín-Vide, C., Truthe, B. (eds.) LATA 2017. LNCS, vol. 10168, pp. 287–298. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-53733-7_21CrossRefMATH

Dang, Z., Ibarra, O.H., Bultan, T., Kemmerer, R.A., Su, J.: Binary reachability analysis of discrete pushdown timed automata. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, pp. 69–84. Springer, Heidelberg (2000). https://doi.org/10.1007/10722167_9CrossRef

Duske, J., Parchmann, R.: Linear indexed languages. Theoret. Comput. Sci. 32(1–2), 47–60 (1984)MathSciNetCrossRef

Ginsburg, S.: Algebraic and Automata-Theoretic Properties of Formal Languages. North-Holland Publishing Company, Amsterdam (1975)MATH

Ginsburg, S., Spanier, E.H.: AFL with the semilinear property. J. Comput. Syst. Sci. 5(4), 365–396 (1971)MathSciNetCrossRef

Hague, M., Lin, A.W.: Synchronisation- and reversal-bounded analysis of multithreaded programs with counters. In: Madhusudan, P., Seshia, S.A. (eds.) CAV 2012. LNCS, vol. 7358, pp. 260–276. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31424-7_22CrossRef

Hague, M., Lin, A.W.: Decidable models of integer-manipulating programs with recursive parallelism. In: Larsen, K.G., Potapov, I., Srba, J. (eds.) RP 2016. LNCS, vol. 9899, pp. 148–162. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45994-3_11CrossRef

10.

Hague, M., Lin, A.W.: Model checking recursive programs with numeric data types. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol. 6806, pp. 743–759. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22110-1_60CrossRef

11.

Harju, T., Ibarra, O.H., Karhumäki, J., Salomaa, A.: Some decision problems concerning semilinearity and commutation. J. Comput. Syst. Sci. 65(2), 278–294 (2002)MathSciNetCrossRef

12.

Harrison, M.: Introduction to Formal Language Theory. Addison-Wesley Series in Computer Science. Addison-Wesley Pub. Co., Boston (1978)MATH

13.

Holzer, M., Kutrib, M.: Flip-pushdown automata: nondeterminism is better than determinism. In: Ésik, Z., Fülöp, Z. (eds.) DLT 2003. LNCS, vol. 2710, pp. 361–372. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-45007-6_29CrossRef

14.

Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)MATH

15.

Ibarra, O.H.: Reversal-bounded multicounter machines and their decision problems. J. ACM 25(1), 116–133 (1978)MathSciNetCrossRef

16.

Ibarra, O.H., Bultan, T., Su, J.: Reachability analysis for some models of infinite-state transition systems. In: Palamidessi, C. (ed.) CONCUR 2000. LNCS, vol. 1877, pp. 183–198. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44618-4_15CrossRef

17.

Ibarra, O.H., Bultan, T., Su, J.: On reachability and safety in infinite-state systems. Int. J. Found. Comput. Sci. 12(6), 821–836 (2001)MathSciNetCrossRef

18.

Ibarra, O.H., Dang, Z.: Eliminating the storage tape in reachability constructions. Theoret. Comput. Sci. 299(1–3), 687–706 (2003)MathSciNetCrossRef

19.

Ibarra, O.H., McQuillan, I.: The effect of end-markers on counter machines and commutativity. Theoret. Comput. Sci. 627, 71–81 (2016)MathSciNetCrossRef

20.

Ibarra, O.H., McQuillan, I.: Variations of checking stack automata: obtaining unexpected decidability properties. In: Charlier, É., Leroy, J., Rigo, M. (eds.) DLT 2017. LNCS, vol. 10396, pp. 235–246. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-62809-7_17CrossRef

21.

Ibarra, O.H., Su, J., Dang, Z., Bultan, T., Kemmerer, R.: Counter machines and verification problems. Theoret. Comput. Sci. 289(1), 165–189 (2002)MathSciNetCrossRef

22.

Ibarra, O.H., Su, J., Dang, Z., Bultan, T., Kemmerer, R.: Counter machines: decidable properties and applications to verification problems. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol. 1893, pp. 426–435. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44612-5_38CrossRef

23.

Parikh, R.: On context-free languages. J. ACM 13(4), 570–581 (1966)CrossRef

24.

Rozenberg, G., Vermeir, D.: On ET0L systems of finite index. Inf. Control 38, 103–133 (1978)CrossRef

25.

Zetzsche, G.: An approach to computing downward closures. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9135, pp. 440–451. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47666-6_35CrossRef

Titel: Semilinearity of Families of Languages
verfasst von: Oscar H. Ibarra
Ian McQuillan
Verlag: Springer International Publishing
Buch: Implementation and Application of Automata
Print ISBN: 978-3-319-94811-9

Electronic ISBN: 978-3-319-94812-6

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-94812-6_18

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner