Properties of Languages with Catenation and Shuffle

• Autorzy: Kudlek M. , Flick N. E.

Identyfikatory

DOI

10.3233/FI-2014-964

• Języki publikacji: EN

Abstrakty

EN

We present structural properties of languages constructed with catenation and shuffle, comprising iteration lemmata and closure properties of the language classes, as well as decidability results that follow.

Słowa kluczowe

EN

language; iterative methods; lamma language; structural analysis; evaluation methodology; decidability

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 129, nr 1/2
• Strony: 117--132
• Opis fizyczny: Bibliogr. 14 poz., tab.

Twórcy

autor

Kudlek M.

• University of Hamburg, Germany

autor

Flick N. E.

• University of Oldenburg, Germany

Bibliografia

• [1] Berglund, Martin; Björklund, Henrik; Högberg, Johanna: Recognizing Shuffle Languages. LNCS 6638, pp. 142-154, 2011.
• [2] Czaja, Ludwik: On Deadlock and Fairness Decision Problems for Computations on Client-server Systems. FI 109 (3) pp. 255–264, 2011.
• [3] Czaja, Ludwik; Kudlek, Manfred: Language Theoretic Properties of Client/Server Systems. Proceedings of CS&P 2011, pp. 79–84, 2011.
• [4] Flick, Nils Erik; Kudlek, Manfred: On A Hierarchy of Languages with Catenation and Shuffle. DLT, LNCS 7410, pp. 452–458, Springer 2012.
• [5] Flick, Nils Erik; Kudlek, Manfred: A Hierarchy of Languages with Catenation and Shuffle, Proceedings of CS&P 2012, pp. 103–114, http://ceur-ws.org/Vol-928/0091.pdf
• [6] Flick, Nils Erik; Kudlek, Manfred: Properties of Languages with Catenation and Shuffle, Proceedings of CS&P 2012, pp. 91–102, http://ceur-ws.org/Vol-928/0091.pdf
• [7] Gischer, Jay: Shuffle Languages, Petri Nets, and Context-sensitive Grammars. CACM 24 (9), pp. 597–605, 1981.
• [8] Jantzen, Matthias: Extending Regular Expressions with Iterated Shuffle. TCS 38, pp. 223–247, 1985.
• [9] J˛edrzejowicz, Joanna and Szepietowski, Andrzej: Shuffle languages are in P, TCS 250, No. 1, pp. 31–53, Elsevier, 2001.
• [10] Kudlek,Manfred: On General Iteration Lemmata for Certain Classes of Word, Trace and Graph Languages. FI 37 (4), pp. 413–422, 1999.
• [11] Kudlek, Manfred: Iteration Lemmata for Normed Semirings., Kyôto University RIMS kôkyuroku 1166, pp. 131–137, 2000.
• [12] Kudlek,Manfred: On Semilinear Sets over Commutative Semirings. FI 79 (3-4), pp. 447–452, 2007.
• [13] Kudlek, Manfred; Martín Vide, Carlos; P˘aun, Gheorghe: Toward FMT (Formal Macroset Theory). In: Multiset Processing, LNCS 2235, pp. 123-133, Springer 2000.
• [14] Kuich,Werner; Salomaa, Arto: Semirings, Automata, Languages. Springer, 1986.