Formal languages | Graph data structures

Abstract semantic graph

In computer science, an abstract semantic graph (ASG) or term graph is a form of abstract syntax in which an expression of a formal or programming language is represented by a graph whose vertices are the expression's subterms. An ASG is at a higher level of abstraction than an abstract syntax tree (or AST), which is used to express the syntactic structure of an expression or program. ASGs are more complex and concise than ASTs because they may contain shared subterms (also known as "common subexpressions"). Abstract semantic graphs are often used as an intermediate representation by compilers to store the results of performing common subexpression elimination upon abstract syntax trees. ASTs are trees and are thus incapable of representing shared terms. ASGs are usually directed acyclic graphs (DAG), although in some applications graphs containing cycles may be permitted. For example, a graph containing a cycle might be used to represent the recursive expressions that are commonly used in functional programming languages as non-looping iteration constructs. The mutability of these types of graphs, is studied in the field of graph rewriting. The nomenclature term graph is associated with the field of term graph rewriting, which involves the transformation and processing of expressions by the specification of rewriting rules, whereas abstract semantic graph is used when discussing linguistics, programming languages, type systems and compilation. Abstract syntax trees are not capable of sharing subexpression nodes because it is not possible for a node in a proper tree to have more than one parent. Although this conceptual simplicity is appealing, it may come at the cost of redundant representation and, in turn, possibly inefficiently duplicating the computation of identical terms. For this reason ASGs are often used as an intermediate language at a subsequent compilation stage to abstract syntax tree construction via parsing. An abstract semantic graph is typically constructed from an abstract syntax tree by a process of enrichment and abstraction. The enrichment can for example be the addition of back-pointers, edges from an identifier node (where a variable is being used) to a node representing the declaration of that variable. The abstraction can entail the removal of details which are relevant only in parsing, not for semantics. (Wikipedia).

Video thumbnail

06 More about mappings

In this tutorial I show a few more notations and share a few more thoughts on mappings.

From playlist Abstract algebra

Video thumbnail

Equivalence Relations Definition and Examples

Please Subscribe here, thank you!!! Equivalence Relations Definition and Examples. This video starts by defining a relation, reflexive relation, symmetric relation, transitive relation, and then an equivalence relation. Several examples are given.

From playlist Abstract Algebra

Video thumbnail

How To Define A Graph

Mathematical theories start with axioms, but penultimate to that is the definition. When we go to learn, what's the best definition to commit to memory? Here we talk about Graph Theory and I give you 3 definitions to choose from. Which would you use?

From playlist Summer of Math Exposition 2 videos

Video thumbnail

Lecture 1 Graphs Definition

A formal definition of a Graph and its properties

From playlist Graph Theory

Video thumbnail

Graph Neural Networks, Session 1: Introduction to Graphs

Examples of Graph representation of data Motivation for doing machine learning on Graphs

From playlist Graph Neural Networks (Hands-on)

Video thumbnail

A Few Conceptual Examples with Statistical Graphs

Please Subscribe here, thank you!!! A Few Conceptual Examples with Statistical Graphs

From playlist Statistics

Video thumbnail

WTF is an Abstract Syntax Tree?

Potential interview question: What is an Abstract Syntax Tree? #shorts #programming #compsci

From playlist Shorts

Video thumbnail

Graph Theory FAQs: 01. More General Graph Definition

In video 02: Definition of a Graph, we defined a (simple) graph as a set of vertices together with a set of edges where the edges are 2-subsets of the vertex set. Notice that this definition does not allow for multiple edges or loops. In general on this channel, we have been discussing o

From playlist Graph Theory FAQs

Video thumbnail

The Definition of a Graph (Graph Theory)

The Definition of a Graph (Graph Theory)

From playlist Graph Theory (Discrete Math)

Video thumbnail

NIPS 2011 Learning Semantics Workshop: Towards More Human-like Machine Learning of Word Meanings

Learning Semantics Workshop at NIPS 2011 Invited Talk: Towards More Human-like Machine Learning of Word Meanings by Josh Tenenbaum Josh Tenenbaum is a Professor in the Department of Brain and Cognitive Sciences at Massachusetts Institute of Technology. Him and his colleagues in the C

From playlist NIPS 2011 Learning Semantics Workshop

Video thumbnail

Compilation - Part Three: Syntax Analysis

This is part three of a series of videos about compilation. Part three is about syntax analysis. It explains how the syntax analyser, otherwise known as the parser, takes a token stream from the lexical analyser, and checks it to make sure that the rules of the source language have been

From playlist Compilation

Video thumbnail

Matteo Valleriani - XAI Historian - IPAM at UCLA

Recorded 12 January 2023. Matteo Valleriani of Technische Universität Berlin presents "XAI Historian" at IPAM's Explainable AI for the Sciences: Towards Novel Insights Workshop. Abstract: Using XAI in historical disciplines, it is possible to turn AI into a research partner from which usef

From playlist 2023 Explainable AI for the Sciences: Towards Novel Insights

Video thumbnail

SOURCE Boston 2008: Automated Structural Malware Classification

Speaker: Ero Carrera With the advent of an economy relying on large bases of infected computers and collection of personal information, malware has become an essential tool for the "harvesters". Such needs and a ready availability of financial resources have propelled the development of f

From playlist SOURCE Boston 2008

Video thumbnail

AI Weekly Update - December 14th, 2020 (#24)!

Thank you for watching! Please Subscribe! Paper / Content Links: Abstraction & Reasoning in Modern AI Systems: Neurosymbolic AI: The 3rd Wave: On the Binding Proble

From playlist AI Research Weekly Updates

Video thumbnail

With Knowledge Doubt Increases - The Significance of Knowledge in Knowledge Graphs

Keynote at 6th International Conference on Graphs and Networks in the Humanities 2022 Prof. Dr. Harald Sack FIZ Karlsruhe - Leibniz Institute for Informaation Infrastructure Karlsruhe Institute of Technology Slides: FIZ ISE on twitter: https:/

From playlist ISE Conference Talks

Video thumbnail

Data Science @Stanford Russ Altman 11/18/2015

Russ Altman discusses extracting genomics knowledge from text and using it for novel inference at the November 18, 2015 Data Science @Stanford seminar.

From playlist Data Science @ Stanford

Video thumbnail

DEFCON 14: RE 2006: New Challenges Need Changing Tools

Speaker: Halvar Flake, CEO of Sabre Security Abstract: Reverse Engineering has come a long way—what used to be practiced behind closed doors is now a mainstream occupation practiced throughout the security industry. Compilers and languages are changing, and the reverse engineer has to ada

From playlist DEFCON 14

Video thumbnail

2 Direct Graphs

Introduction to graph theory. Directed and undirected graph

From playlist Graph Theory

Related pages

Directed acyclic graph | Term (logic) | Graph rewriting | Logical consequence | Graph (discrete mathematics) | Iteration | Abstract syntax tree | Cycle (graph theory) | Formal language | Common subexpression elimination | Parsing