Generative Capacity of Contextual Grammars with Subregular Selection Languages

• Autorzy: Truthe Bianca

Identyfikatory

DOI

10.3233/FI-2021-2037

• Języki publikacji: EN

Abstrakty

EN

A contextual grammar is a language generating mechanism inspired by generating sentences in natural languages. An existing string can be extended to a new string of the language by adjoining a context before and behind the string or by inserting it into the string around some subword. The first mode is called external derivation whereas the second mode is called internal derivation. If conditions are given, around which words which contexts can be adjoined, we speak about contextual grammars with selection. We give an overview about the generative capacity of contextual grammars (working externally or internally) where the selection languages belong to subregular language classes. All languages generated by contextual grammars where all selection languages are elements of a certain subregular language family form again a language family. We compare such families which are based on finite, monoidal, nilpotent, combinational, definite, suffix-closed, ordered, commutative, circular, non-counting, power-separating, or union-free languages, or based on languages defined by restrictions regarding the descriptional complexity.

Słowa kluczowe

EN

contextual grammars; subregular language families; formal languages; generative power

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 180, nr 1-2
• Strony: 123--150
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Truthe Bianca

• Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany

Bibliografia

• [1] Truthe B. Hierarchies of Language Families of Contextual Grammars. In: Freund R, Mráz F, Průša D (eds.), Nineth Workshop on Non-Classical Models of Automata and Applications (NCMA), Prague, Czech Republic, August 17-18, 2017, Proceedings, volume 329 of [e-mail]. Österreichische Computer Gesellschaft, 2017 pp. 13-28.
• [2] Marcus S. Contextual grammars. Revue Roum. Math. Pures Appl., 1969. 14:1525-1534.
• [3] Istrail S. Gramatici contextuale cu selectiva regulata. Stud. Cerc. Mat., 1978. 30:287-294. MR50080368F05.
• [4] Rozenberg G, Salomaa A (eds.). Handbook of Formal Languages. Springer-Verlag, Berlin, 1997. ISBN: 978-3-642-63863-3.
• [5] Păun G. Marcus Contextual Grammars. Kluwer Publ. House, Dordrecht, 1998. doi:10.1007/978-94-015-8969-7.
• [6] Dassow J, Manea F, Truthe B. Networks of evolutionary processors: the power of subregular filters. Acta Informatica, 2013. 50(1):41-75. doi:10.1007/s00236-012-0172-0.
• [7] Dassow J. Contextual grammars with subregular choice. Fundamenta Informaticae, 2005. 64(1-4):109-118.
• [8] Dassow J, Manea F, Truthe B. On Contextual Grammars with Subregular Selection Languages. In: Holzer M, Kutrib M, Pighizzini G (eds.), Descriptional Complexity of Formal Systems - 13th International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011. Proceedings, volume 6808 of LNCS. Springer-Verlag, 2011 pp. 135-146. doi:10.1007/978-3-642-22600-7_11.
• [9] Manea F, Truthe B. On Internal Contextual Grammars with Subregular Selection Languages. In: Kutrib M, Moreira N, Reis R (eds.), Descriptional Complexity of Formal Systems - 14th International Workshop, DCFS 2012, Braga, Portugal, July 23-25, 2012. Proceedings, volume 7386 of LNCS. Springer-Verlag, 2012 pp. 222-235. doi:10.1007/978-3-642-31623-4_17.
• [10] Dassow J, Manea F, Truthe B. On External Contextual Grammars with Subregular Selection Languages. Theoretical Computer Science, 2012. 449(1):64-73. doi:10.1016/j.tcs.2012.04.008.
• [11] Dassow J, Manea F, Truthe B. On Subregular Selection Languages in Internal Contextual Grammars. Journal of Automata, Languages, and Combinatorics, 2012. 17(2-4):145-164. doi:10.25596/jalc-2012-145.
• [12] Wiedemann B. Vergleich der Leistungsfähigkeit endlicher determinierter Automaten. Diplomarbeit, Universität Rostock, 1978.
• [13] Havel IM. The theory of regular events II. Kybernetika, 1969. 5(6):520-544. ISSN:0023-5954.
• [14] Shyr H, Thierrin G. Ordered Automata and Associated Languages. Tankang Journal of Mathematics, 1974. 5(1):9-20.
• [15] Holzer M, Truthe B. On Relations Between Some Subregular Language Families. In: Freund R, Holzer M, Moreira N, Reis R (eds.), Seventh Workshop on Non-Classical Models of Automata and Applications (NCMA), Porto, Portugal, August 31-September 1, 2015, Proceedings, volume 318 of [e-mail]. Österreichische Computer Gesellschaft, 2015 pp. 109-124.
• [16] Shyr H, Thierrin G. Power-Separating Regular Languages. Mathematical Systems Theory, 1974. 8(1):90-95. doi:10.1007/BF01761710.
• [17] Truthe B. Hierarchy of Subregular Language Families. Technical report, Justus-Liebig-Universität Giessen, Institut für Informatik, IFIG Research Report 1801, 2018. URL http://geb.uni-giessen.de/geb/volltexte/2018/13478/.
• [18] Truthe B. A Relation Between Definite and Ordered Finite Automata. In: Bensch S, Freund R, Otto F (eds.), Sixth Workshop on Non-Classical Models of Automata and Applications (NCMA), Kassel, Germany, July 28-29, 2014, Proceedings, volume 304 of [e-mail]. Österreichische Computer Gesellschaft, 2014 pp. 235-247.
• [19] Dassow J. Grammars with control by ideals and codes. Journal of Automata, Languages and Combinatorics, 2018. 23(1-3):143-164. doi:10.25596/jalc-2018-143.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).