Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
An Exercise in Mathematical Engineering: Stating and Proving Kuratowski Theorem Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Quotients of Unbounded Parallelism

verfasst von : Nils Erik Flick

Erschienen in: Theoretical Aspects of Computing - ICTAC 2015

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

This is a language-theoretic investigation into a situation where a server serves an unbounded number of requests, and handling a request requires a bounded number of (arbitrarily delayed) steps. From a description of the system in interleaving semantics, one endeavours to determine whether some sequence from a given regular language is possible. We model unbounded parallelism using the iterated shuffle operator, investigate quotients of the so-called simple shuffled languages with regular languages, and prove a sufficient condition for obtaining another simple shuffled language by that operation.

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 Rigid Families for CCS and the -calculus
Nächstes Kapitel Higher-Order Dynamics in Event Structures
Fußnoten
1
The dots indicate that the transition system may have further structure, such as initial states or labels. This notation stems from [10].
 
2
The order of the \(P'\) letters in \(A^-(t)\) could just as well be fixed, but \(\psi ^{-1}\) is required so the P letters can appear wherever they are needed.
 
3
Equivalently described in [12] as a “Vector Addition System with States” (VASS).
 
Literatur
1.
Baeten, J., Bergstra, J., Klop, J.: An operational semantics for process algebra. Centrum voor Wiskunde en Informatica, Department of Computer Science (1985)
2.
Berglund, M., Björklund, H., Högberg, J.: Recognizing shuffled languages. In: Dediu, A.-H., Inenaga, S., Martín-Vide, C. (eds.) LATA 2011. LNCS, vol. 6638, pp. 142–154. Springer, Heidelberg (2011) CrossRef
3.
Berstel, J.: Transductions and Context-Free Languages, vol. 4. Teubner, Stuttgart (1979)CrossRefMATH
4.
Berstel, J., Boasson, L., Carton, O., Pin, J.E., Restivo, A.: The expressive power of the shuffle product. Inf. Comput. 208(11), 1258–1272 (2010)MathSciNetCrossRefMATH
5.
6.
7.
Castiglione, G., Restivo, A.: On the shuffle of star-free languages. Fundam. Inform. 116(1–4), 35–44 (2012)MathSciNetMATH
8.
9.
10.
11.
Flick, N.E., Kudlek, M.: On a hierarchy of languages with catenation and shuffle. In: Yen, H.-C., Ibarra, O.H. (eds.) DLT 2012. LNCS, vol. 7410, pp. 452–458. Springer, Heidelberg (2012) CrossRef
12.
Hopcroft, J., Pansiot, J.J.: On the reachability problem for 5-dimensional vector addition systems. Theor. Comput. Sci. 8(2), 135–159 (1979)MathSciNetCrossRefMATH
13.
14.
15.
Kudlek, M., Flick, N.E.: A hierarchy of languages with catenation and shuffle. Fundam. Inform. 128(1–2), 113–128 (2013)MathSciNetMATH
16.
Kudlek, M., Flick, N.E.: Properties of languages with catenation and shuffle. Fundam. Inform. 129(1–2), 117–132 (2014)MathSciNetMATH
17.
Kudlek, M., Martín-Vide, C., Paun, G.: Toward a formal macroset theory. In: Calude, C.S., Pun, G., Rozenberg, G., Salomaa, A. (eds.) Multiset Processing. LNCS, vol. 2235, pp. 123–133. Springer, Heidelberg (2001) CrossRef
18.
Kuich, W., Salomaa, A.: Semirings, Automata, Languages. EATCS monographs on theoretical computer science. Springer, Heidelberg (1986) CrossRefMATH
19.
Latteux, M., Leguy, B., Ratoandromanana, B.: The family of one-counter languages is closed under quotient. Acta Informatica 22(5), 579–588 (1985)MathSciNetMATH
20.
Lipton, R.: The reachability problem requires exponential space. Research Report 62, Department of Computer Science, Yale University, New Haven, Connecticut (1976)
21.
Pin, J.É., Sakarovitch, J.: Some operations and transductions that preserve rationality. In: Cremers, A.B., Kriegel, H.-P. (eds.) Theoretical Computer Science. LNCS, vol. 145, pp. 277–288. Springer, Heidelberg (1982)CrossRef
22.
Starke, P.H.: Free petri net languages. In: Winkowski, J. (ed.) Mathematical Foundations of Computer Science 1978. LNCS, vol. 64, pp. 506–515. Springer, Heidelberg (1978)CrossRef
23.
24.
Wimmel, H.: Entscheidbarkeit bei Petri Netzen Überblick und Kompendium. Springer, Heidelberg (2008)
25.
Metadaten
Titel
Quotients of Unbounded Parallelism
verfasst von
Nils Erik Flick
Copyright-Jahr
2015
Buch
Theoretical Aspects of Computing - ICTAC 2015

Print ISBN: 978-3-319-25149-3

Electronic ISBN: 978-3-319-25150-9

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-25150-9_15