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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Separating Topological Noise from Features Using Persistent Entropy Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Approximating Parikh Images for Generating Deterministic Graph Parsers

verfasst von : Frank Drewes, Berthold Hoffmann, Mark Minas

Erschienen in: Software Technologies: Applications and Foundations

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The Parikh image of a word abstracts from the order of its letters. Parikh’s famous theorem states that the set of Parikh images of a context-free string language forms a semilinear set that can be effectively computed from its grammar. In this paper we study the computation of Parikh images for graph grammars defined by contextual hyperedge replacement (CHR). Our motivation is to generate efficient predictive top-down (PTD) parsers for a subclass of CHR grammars. We illustrate this by describing the subtask that identifies the nodes of the input graph that parsing starts with.

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 On the Definition of Parallel Independence in the Algebraic Approaches to Graph Transformation
Nächstes Kapitel SPO-Rewriting of Constrained Partial Algebras
Fußnoten
1
Due to space restrictions, that paper describes only the HR case.
 
2
[n] denotes the set \(\{1, \dots , n\}\).
 
3
Note that a node with just a leaving \(\textit{goto}\) edge can actually not be a starting node although this is indicated by \(\psi ''(S^x_{\textsf {i}})\). The reason for this over-approximation is that rule \([\textsf {g}]_{x}\) can be be applied to \(D(\bullet )\) even if there is no additional node that could be used as a context node, which is actually necessary for applying CHR rule g.
 
Literatur
1.
2.
Costagliola, G., Chang, S.K.: Using linear positional grammars for the LR parsing of 2-D symbolic languages. Grammars 2(1), 1–34 (1999)MathSciNetCrossRefMATH
3.
4.
Drewes, F., Hoffmann, B., Minas, M.: Predictive top-down parsing for hyperedge replacement grammars. In: Parisi-Presicce, F., Westfechtel, B. (eds.) ICGT 2015. LNCS, vol. 9151, pp. 19–34. Springer, Heidelberg (2015). doi:10.​1007/​978-3-319-21145-9_​2 CrossRef
5.
Esparza, J., Kiefer, S., Luttenberger, M.: Newton’s method for \(Omega\)-continuous semirings. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 14–26. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-70583-3_​2 CrossRef
6.
7.
8.
9.
Ibarra, O.H., Seki, S.: Characterizations of bounded semilinear languages by one-way and two-way deterministic machines. Int. J. Found. Comput. Sci. 23(6), 1291–1305 (2012)MathSciNetCrossRefMATH
10.
Kaul, M.: Practical applications of precedence graph grammars. In: Ehrig, H., Nagl, M., Rozenberg, G., Rosenfeld, A. (eds.) Graph Grammars 1986. LNCS, vol. 291, pp. 326–342. Springer, Heidelberg (1987). doi:10.​1007/​3-540-18771-5_​62 CrossRef
11.
Lavado, G.J., Pighizzini, G., Seki, S.: Converting nondeterministic automata and context-free grammars into Parikh equivalent deterministic automata. In: Yen, H.-C., Ibarra, O.H. (eds.) DLT 2012. LNCS, vol. 7410, pp. 284–295. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-31653-1_​26 CrossRef
12.
13.
To, A.W.: Model checking infinite-state systems: generic and specific approaches. Ph.D. thesis, School of Informatics, University of Edinburgh, August 2010
Metadaten
Titel
Approximating Parikh Images for Generating Deterministic Graph Parsers
verfasst von
Frank Drewes
Berthold Hoffmann
Mark Minas
Copyright-Jahr
2016
Buch
Software Technologies: Applications and Foundations

Print ISBN: 978-3-319-50229-8

Electronic ISBN: 978-3-319-50230-4

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-50230-4_9

Premium Partner

    Bildnachweise