Czasopismo
2013
|
Vol. 128, nr 1-2
|
113--128
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Warianty tytułu
Języki publikacji
Abstrakty
We present basic structures, definitions, normal forms, and a hierarchy of languages based on catenation, shuffle and their iterations, defined by algebraic closures or least fixed point solutions to systems of equations.
Czasopismo
Rocznik
Tom
Strony
113--128
Opis fizyczny
Bibliogr. 27 poz., rys.
Twórcy
autor
- University of Hamburg, Germany
autor
- University of Oldenburg, Germany, flick@informatik.uni-oldenburg.de
Bibliografia
- [1] Berglund, Martin; Björklund, Henrik; Högberg, Johanna: Recognizing Shuffled Languages. LNCS 6638, pp. 142-154, 2011.
- [2] Berglund, Martin: Complexities of Parsing in the Presence of Reordering, Licent. thesis, Department of Computing Science, Umeâ University, 2012.
- [3] Berstel, Jean; Boasson, Luc; Carton, Olivier; Pin, Jean-Éric; Restivo, Antonio: The Expressive Power of the Shuffle Product, Information and Computation 208 (2010), no. 11, 1258-1272.
- [4] Bloom, Stephen L.; Ésik, Zoltan: Axiomatizing Shuffle and Concatenation in Languages, Information and Computation 139 (1997), no. 1, 62-91.
- [5] Câmpeanu, Cezar; Salomaa, Kai; Vagvolgyi, Sandor: Shuffle Quotient and Decomposition. Springer LNCS 2295, pp. 186-196, 2002.
- [6] Czaja, Ludwik; Kudlek, Manfred: Language Theoretic Properties of Client/Server Systems. Proceedings of CS&P 2011, pp. 79-84, 2011.
- [7] Czerwiński, Wojciech; Fröschle, Sibylle; Lasota, Sławomir: Partially-Commutative Context-Free Processes: Expressibility and Tractability, Information and Computation 209 (2011), no. 5, 782 - 798.
- [8] Czerwmski, Wojciech; Lasota, Sławomir: Partially-Commutative Context-Free Languages. EPTCS 89, pp. 35-48, 2012.
- [9] Ésik, Zoltan; Bertol, Michael: Nonfinite Axiomatizability of the Equational Theory of Shuffle, Automata, Languages and Programming (1995), 27-38.
- [10] Esparza, Javier: Petri Nets, Commutative Context-Free Grammars, and Basic Parallel Processes, Springer LNCS 965, 1995, pp. 221-232.
- [11] Flick, Nils Erik; Kudlek, Manfred: On a Hierarchy of Languages with Catenation and Shuffle, DLT 2012, LNCS 7410, pp. 452-458, 2012.
- [12] Flick, Nils Erik; Kudlek, Manfred: A Hierarchy of Languages with Catenation and Shuffle, Proceedings of CS&P 2012, pp. 103-114, 2012.
- [13] Flick, Nils Erik; Kudlek, Manfred: Properties of Languages with Catenation and Shuffle, Proceedings of CS&P 2012, pp. 91-102, 2012.
- [14] Ginsburg, Seymour: The Mathematical Theory of Context-Free Languages. McGraw-Hill, 1966.
- [15] Gischer, Jay: Shuffle Languages, Petri Nets, and Context-sensitive Grammars. CACM 24 (9), pp. 597-605, 1981.
- [16] Ito, Masami: Shuffle Decomposition of Regular Languages. Journal of Universal Computer Science, Vol. 8, No. 2, pp. 257-259, 2002.
- [17] Ito, Masami: Algebraic Theory of Automata and Languages. World Scientific, 2004.
- [18] Jantzen, Matthias: The Power of Synchronizing Operations on Strings. Technical Report, FB Informatik, Univ. Hamburg, IfI-HH-B-67/80, 1980.
- [19] Jedrzejowicz, Joanna: Nesting of Shuffle Closure is Important, Inf. Process. Lett. (1987), 363-368.
- [20] Jedrzejowicz, Joanna: Infinite hierarchy of expressions containing shuffle closure operator. Inf. Proccess. Lett. 28 (1988), 33 - 37.
- [21] Jantzen, Matthias: Extending Regular Expressions with Iterated Shuffle. TCS 38, pp. 223-247, 1985.
- [22] Kudlek, Manfred: On General Iteration Lemmata for Certain Classes of Word, Trace and Graph Languages. FI 37 (4), pp. 413-422, 1999.
- [23] Kudlek, Manfred: On Semilinear Sets over Commutative Semirings. FI 79 (3-4), pp. 447-452, 2007.
- [24] Kuich, Werner; Salomaa, Arto: Semirings, Automata, Languages. Springer, 1986.
- [25] Mazurkiewicz, Antoni: Introduction to Trace Theory, in: Diekert, Volker; Rozenberg, Grzegorz (eds.): The Book of Traces (1995), 3-41.
- [26] Szepietowski, Andrzej: There is no Complete Axiom System for Shuffle Expressions, ITA 33 (1999), no. 3, 271-277.
- [27] Tschantz, Steven T.: Languages under Concatenation and Shuffling, MSCS 4 (1994), no. 4, 505-511.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-6960e0f6-a2c9-4fdf-b4b3-1da5a54801ea