21 skills found
lukstafi / Curious OcamlA curious book about OCaml: logic (types), algebra (values), computation (semantics), functions (lambda calculus), constraints, monads, algebraic effects, expression.
nert-nlp / AMR BibliographyOrganized inventory of research using the Abstract Meaning Representation
decompositional-semantics-initiative / DNCDiverse Natural Language Inference Collection - NLI dataset that can used to evaluate how well models perform distinct types of reasoning (EMNLP 2018)
DigitalFormalLogic / MathesisPython library for computational formal logic, formal semantics, and theorem proving
BlockchainLabs / SpreadCoinSpreadCoin October 5, 2014 Introduction In proof-of-work cryptocurrencies new coins are generated by the network through the process of mining. One of the purposes of mining is to protect network from double spending attacks and history rewriting. Miners generate new blocks and check contents of the blocks generated by other peers for conformation to the network rules. However, many miners now delegate all the checking work crucial to cryptocurrency security to pools. This means that pool operators do not have any large hashing power but have control over generation of new blocks. This brings unnecessary centralization to otherwise decentralized system. Controlling more than 50% of mining power allows to perform double-spending attacks with 100% chance of success but even with less than 50% control it is possible to perform attacks which have chances to succeed1 . The core idea of SpreadCoin is to prevent creation of pools and thus make mining more decentralized and the whole system more secure. Pool Prevention In pooled mining miners perform only the work which is necessary to fulfill the proof-of-work requirements and pools take care of block generation and broadcasting and distribute reward among miners according to the shares they submit. In this scheme miner has two alternatives: 1. Solo mining. In this case miner cannot send shares to the pool because they will not be accepted. 2. Pooled mining. Miner’s shares will be accepted by the pool but in the case miner will actually generate a new block its reward will go to the pool which will redistribute it to all miners. This allows organization of pools because miners has no way to cheat and steal generated money. To prevent creation of pools we must remove this possibility so that if pool will be created than miner can mine in a pool, submit shares as usual and get reward for them but in the case of actually finding a block miner can send it directly to the network instead of the pool and get full reward for it. In SpreadCoin mining is organized in such way that miner must know the following things: 1. Private key corresponding to the coinbase transaction. 2. Whole block, not only its header. This ensures that miner can broadcast mined block and spend coins generated in that block. It may seem that it is necessary to know only the private key to spend coinbase transaction. If two conflicting transactions will appear on the network then the one that was broadcasted first will have much higher probability to be included in a block because each peer remembers and retransmits only the first one of the conflicting transactions. If both miner and pool know private key but only pool knows the content of the block than pool can generate and broadcast spending transaction earlier than miner. If both miner 1 Double-spending. Bitcoin Wiki. https://en.bitcoin.it/wiki/Double-spending and pool know content of the block than miner will be the first one who can broadcast block and spending transaction. To prove knowledge of the private key and whole block there are two new fields in the block header: MinerSignature and hashWholeBlock. MinerSignature is a digital signature of all fields of the block header except for the hashWholeBlock. Changing any information in the block requires regeneration of this signature which means that it is necessary to recalculate it during each iteration of the mining process. This implies that miner must be able to sign any arbitrary data. hashWholeBlock is a SHA-256 hash of the block data arranged as follows: Padding ensures that there is no incentive to mine empty blocks without transactions. Padding values are computed using simple algorithm which initializes last 32 bytes (8 uint32) with hashPrevBlock and then goes backward and computes remaining uint32 values using the following recursive formula: 𝐼𝑖 = 𝐼𝑖+3 ∙ 𝐼𝑖+7. This algorithm ensures that there is no efficient way to compute padding values on the fly during hash computation which otherwise could potentially give some advantage to mine empty blocks in certain computing environments. It is important that block is hashed twice. If it was hashed only once then pool could hash the beginning of the block and send resulting hash state to the miners. Each miner would then modify some information in the end of the block and recalculate the hash based on the known state without actual knowledge about what is contained in the beginning of the block. Appending block data to itself make it necessary to know the whole block to recalculate hashWholeBlock. Pool may detect and ban cheating miners. However, many miners may still prefer to cheat so that pool will be completely unusable for honest miners. Miners that have low probability of finding a block will get more profit by stealing reward for accidentally found block even if pool will ban them thereafter. Miners that have enough mining power to find blocks consistently can still connect to a pool and submit shares for some time but steal the first found block. This way they can get both reward for their shares and the actual mined block. Given all this it is expected that no one will create a pool. But even if someone will than it can be countered by releasing stealing miner software which many miners will switch to. Compact Transactions SpreadCoin as well as Bitcoin uses ECDSA signatures. Each address in Bitcoin is a hash of an ECDSA public key. To spend coins sent to an address it is necessary to provide public key matching to that hash and a signature. This results in 139 or 107 bytes for each transaction input script (scriptSig) depending on Block Padding MAX_BLOCK_SIZE Block Padding whether compact public key is used. However, it is possible to recover public key from the signature2 which means that it is not necessary to provide it in transaction input. Together with using compact representation of the signature3 it allows to reduce size of transaction input script from 139 or 107 bytes in Bitcoin to 67 bytes in SpreadCoin. Recovering public key has almost no extra CPU cost compared to the usual signature verification process used in Bitcoin. This is important because the CPU cost of ECDSA signature verification is a bottleneck for Bitcoin transaction processing. Usual output script (scriptPubKey) in Bitcoin looks as follows: OP_DUP OP_HASH160 5bd18804e4bb43a4bb8b6bc88408970bafaf4a38 OP_EQUALVERIFY OP_CHECKSIG In SpreadCoin the semantics of the OP_CHECKSIG instruction was changed to checking signature by hash of the public key (it recovers public key and compares its hash with the provided one). This results in a much simpler script in SpreadCoin: 5bd18804e4bb43a4bb8b6bc88408970bafaf4a38 OP_CHECKSIG This results in additional minor space saving because this script is 3 bytes smaller. Smooth Supply Block reward in Bitcoin is computed using the following formula: 𝑅ℎ = 𝑅0 ∙ 2 −⌊ ℎ 𝑝 ⌋ , where ℎ – block height, 𝑝 – reward halving period, 𝑅0 – initial reward, 𝑅ℎ – reward for block ℎ, ⌊ ⌋ – floor function. This method results in abrupt reward changes near halving points. SpreadCoin uses simple linear interpolation between halving points to make reward decrease much smother. This is achieved by modifying reward using the following formula: 𝑅ℎ ′ = 4 3 (𝑅ℎ − 𝑅ℎ ∙ ℎ mod 𝑝 2𝑝 ). SpreadCoin uses 𝑝 = 2 ∙ 106 as its reward halving period. 2 ECDSA Signatures allow recovery of the public key. Bitcoin Forum. https://bitcointalk.org/?topic=6430.0%29%3F 3 Why the signature is always 65 (1+32+32) bytes long? Bitcoin Stack Exchange. https://bitcoin.stackexchange.com/questions/12554/why-the-signature-is-always-65-13232-bytes-long | NO YEAR 2106 PROBLEM The time stamp field in the block header is now 64 bit instead of 32 bit (Bitcoin) so that much farther date times are possible (>Year 2106) Upcoming features that are in development and will be introduced over the next weeks and months: SERVICENODES A servicenode is a node which runs continuously (24/7) on a server and which provides services within the spreadcoin network. You have to pay a collateral to be able to install a servernode (in return your servicenode will earn a steady income). This collateral is determined by a free market price discovery. (No fix collateral. The price is allowed to fluctuate over time.) COMPETITIVE COLLATERAL Furthermore, to introduce a competitive nature to the servicenodes there will only ever be a limited number of allowed servicenodes worldwide. Since the collateral isn't set in stone, but the amount of servicenodes is fixed, the price of a servicenode will be determined by the participants themselves. It is expected that the price will vary widely over time, which exposes it to the same market forces that hashrate and currency value are exposed to too. SERVICE APPS There are a number of decentralized applications that will run on servicenodes. Most likely those apps will include: 1) "Spread the message" (an in-wallet encrypted messaging system, which allows you to send a message to an SPR address) 2) "Spread the Search" (A decentralized search engine that lets the servicenodes crawl and map the entire internet.) . SPREADX11 SpreadX11 is different from plain X11 by introducing a sophisticated pool prevention mechanism. With SpreadX11 every block header contains additional information (MinerSignature and hashWholeBlock). With the help of this information the protocol ensures that the miner of a new block is always also the first one to know the content of the whole block and the private key to spend the coinbase transaction. (contrary to pool mining where the pool operator is the first one to know those things) So when a miner finds a block, he must himself sign and transmit the block to the network (like solo mining), instead of having a pool handle this for him. This effectively prevents pools by making their rules non-enforceable, since any miner in any assumed pool can always just steal the block reward instead of following the rules set up by the pool. COMPACT TRANSACTIONS SpreadCoin uses a more compact representation for signatures in transactions. SpreadCoin as well as Bitcoin uses ECDSA signatures. While bitcoin keeps a copy of the public key of the corresponding signature around, SpreadCoin ommits this by recovering the public key on the fly directly from the signature. This way it is not necessary to keep the public key of every ECDSA signature in the blockchain, so this leads to *smaller transactions and hence a smaller blockchain (at the cost of a few CPU cycles more). (*reduction in size of transaction from 139 or 107 bytes in Bitcoin to 67 bytes in SpreadCoin.) SMOOTH HALVING Unlike Bitcoin, there are no abrupt reward halvings in SpreadCoin. Block reward is smoothly decreasing over time. UNIQUE DESIGN WITH IN-WALLET VANITYGEN One of the first apps to be built into the wallet is the vanity generator (or vanity gen) which allows anyone to create personalised payment addresses. The easy to use wallet lets you search through trillions of payment addresses allowing you to find one or multiple vanity addresses, which are then stored safely along with the private keys on your own computer - and nowhere else. Searching using the vanity gen is probabilistic, so the amount of time required to find your chosen address patterns depends on how complex the pattern is, the speed of your computer, and a little bit of luck. You can use the vanity gen for a bit of fun, to make your address standout from the crowd or to create a link to a brand, business or other organisation. You can even search for addresses that others might be willing to buy from you. SpreadCoin is a new cryptocurrency which is more decentralized than Bitcoin. It prevents centralization of hashing power in pools, which is one of the main concerns of Bitcoin security. SpreadCoin was fairly launched on 29 July 2014, 9:00 UTC with no premine.
eric11eca / NeuralLogA neural-symbolic joint reasoning approach for Natural Language Inference (NLI). Modeling NLI as inference path planning through a search engine. Sequence chunking and neural paraphrase detection for syntactic variation. SOTA result on SICK and MED.
umutozge / Computational SemanticsCOGS 543 - Computational Semantics
Sahrawat1 / Semantic Textual SimilarityAbstract Semantic Textual Similarity (STS) measures the meaning similarity of sentences. Applications of this task include machine translation, summarization, text generation, question answering, short answer grading, semantic search, dialogue and conversational systems. We developed Support Vector Regression model with various features including the similarity scores calculated using alignment-based methods and semantic composition based methods. We have also trained sentence semantic representations with BiLSTM and Convolutional Neural Networks (CNN). The correlations between our system output the human ratings were above 0.8 in the test dataset. Introduction The goal of this task is to measure semantic textual similarity between a given pair of sentences (what they mean rather than whether they look similar syntactically). While making such an assessment is trivial for humans, constructing algorithms and computational models that mimic human level performance represents a difficult and deep natural language understanding (NLU) problem. Example 1: English: Birdie is washing itself in the water basin. English Paraphrase: The bird is bathing in the sink. Similarity Score: 5 ( The two sentences are completely equivalent, as they mean the same thing.) Example 2: English: The young lady enjoys listening to the guitar. English Paraphrase: The woman is playing the violin. Similarity Score: 1 ( The two sentences are not equivalent, but are on the same topic. ) Semantic Textual Similarity (STS) measures the degree of equivalence in the underlying semantics of paired snippets of text. STS differs from both textual entailment and paraphrase detection in that it captures gradations of meaning overlap rather than making binary classifications of particular relationships. While semantic relatedness expresses a graded semantic relationship as well, it is non-specific about the nature of the relationship with contradictory material still being a candidate for a high score (e.g., “night” and “day” are highly related but not particularly similar). The task involves producing real-valued similarity scores for sentence pairs. Performance is measured by the Pearson correlation of machine scores with human judgments.
aindilis / Eurisko ResourcesResources to parse into computational semantics in order to enable model checkers to regenerate and extend a program resembling the original Eurisko and related systems.
eric11eca / Udep2MonoUniversal Dependency polarization for monotonicity based natural language inference
letuananh / Intsem.fxA Python 3 implementation of the Integrated Semantic Framework that provides computational deep semantic analysis by combining structural semantics from construction grammars and lexical semantics from ontologies in a single representation.
dorchard / Computational SemanticsFork of the code examples from "Computational Semantics with Functional Programming" (Eijck, Unger) http://www.computational-semantics.eu/
sdobnik / Computational Semantics Vt21Course materials for Computational Semantics LT2213, second edition
GPPassos / Computational SemanticsRepository for Bachelor's Thesis (final project) in Applied Mathematics at Fundação Getulio Vargas
schar / Comp SemComputational Semantics seminar materials (615:535, S17)
jacopotagliabue / Tarski 2.0Old-style computational semantics at the time of Python 3.6
losyer / CsmwpShota Sasaki, Sho Takase, Naoya Inoue, Naoaki Okazaki and Kentaro Inui. "Handling Multiword Expressions in Causality Estimation". In Proceedings of 12th International Conference on Computational Semantics (IWCS).
robincooper / Prolog And Natural Language SemanticsUsed for teaching computational semantics in 80's and 90's
epowers / MpfrProvides a library for multiple-precision floating-point computation with correct rounding. The computation is both efficient and has a well-defined semantics. It copies the good ideas from the ANSI/IEEE-754 standard for double-precision FP arithmetic.
VakinduPhilliam / Python Filesystem MechanicsThe following scripts are written to demonstrate file handling and management modules in Python. The library modules explored include; LZMA: compression using the LZMA algorithm. This module provides classes and convenience functions for compressing and decompressing data using the LZMA compression algorithm. Also included is a file interface supporting the .xz and legacy .lzma file formats used by the xz utility, as well as raw compressed streams. The interface provided by this module is very similar to that of the bz2 module. However, note that LZMAFile is not thread-safe, unlike bz2.BZ2File, so if you need to use a single LZMAFile instance from multiple threads, it is necessary to protect it with a lock. GZIP: Support for gzip files. This module provides a simple interface to compress and decompress files just like the GNU programs gzip and gunzip would. The data compression is provided by the zlib module. The gzip module provides the GzipFile class, as well as the open(), compress() and decompress() convenience functions. The GzipFile class reads and writes gzip-format files, automatically compressing or decompressing the data so that it looks like an ordinary file object. Tarfile: read and write tar archive files. The tarfile module makes it possible to read and write tar archives, including those using gzip, bz2 and lzma compression. Use the zipfile module to read or write .zip files, or the higher-level functions in shutil. Plistlib: generate and parse Mac OS X .plist files. This module provides an interface for reading and writing the “property list” files used mainly by Mac OS X and supports both binary and XML plist files. The property list (.plist) file format is a simple serialization supporting basic object types, like dictionaries, lists, numbers and strings. Usually the top level object is a dictionary. To write out and to parse a plist file, use the dump() and load() functions. To work with plist data in bytes objects, use dumps() and loads(). Values can be strings, integers, floats, booleans, tuples, lists, dictionaries (but only with string keys), Data, bytes, bytesarray or datetime.datetime objects. Fnmatch: unix filename pattern matching. This module provides support for Unix shell-style wildcards, which are not the same as regular expressions. Glob: unix style pathname pattern expansion. The glob module finds all the pathnames matching a specified pattern according to the rules used by the Unix shell, although results are returned in arbitrary order. No tilde expansion is done, but *, ?, and character ranges expressed with [] will be correctly matched. This is done by using the os.scandir() and fnmatch.fnmatch() functions in concert, and not by actually invoking a subshell. Pathlib: object-oriented filesystem paths. This module offers classes representing filesystem paths with semantics appropriate for different operating systems. Path classes are divided between 'pure paths', which provide purely computational operations without I/O, and 'concrete paths', which inherit from pure paths but also provide I/O operations. Fileinput: iterate over lines from multiple input streams. This module implements a helper class and functions to quickly write a loop over standard input or a list of files. Filecmp: file and Directory Comparisons. The filecmp module defines functions to compare files and directories, with various optional time/correctness trade-offs. Tempfile: generate temporary files and directories. This module creates temporary files and directories. It works on all supported platforms. TemporaryFile, NamedTemporaryFile, TemporaryDirectory, and SpooledTemporaryFile are high-level interfaces which provide automatic cleanup and can be used as context managers. mkstemp() and mkdtemp() are lower-level functions which require manual cleanup. Compiled and presented by Vakindu Philliam.
