PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

A Hierarchy of Languages with Catenation and Shuffle

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Strony
113--128
Opis fizyczny
Bibliogr. 27 poz., rys.
Twórcy
autor
  • University of Hamburg, Germany
autor
  • University of Oldenburg, Germany
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
Identyfikator YADDA
bwmeta1.element.baztech-6960e0f6-a2c9-4fdf-b4b3-1da5a54801ea
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.