Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLexical State Analyzer
87
0
0.0
(
0
)
Added by
Kartik Gupta
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Lexical states provide a powerful mechanism to scan regular expressions in a context sensitive manner. At the same time, lexical states also make it hard to reason about the correctness of the grammar. We first categorize the related correctness issues into two classes: errors and warnings, and then present a context sensitive and a context insensitive analysis to identify errors and warnings in context-free-grammars (CFGs). We also present a comparative study of these analyses. A standalone tool (LSA) has also been implemented by us that can identify errors and warnings in JavaCC grammars. The LSA tool outputs a graph that depicts the grammar and the error transitions. It can also generates counter example strings that can be used to establish the errors. We have used LSA to analyze a host of open-source JavaCC grammar files to good effect.
rate research
Read More
Most scripting languages nowadays use regex pattern-matching libraries. These regex libraries borrow the syntax of regular expressions, but have an informal semantics that is different from the semantics of regular expressions, removing the commutativity of alternation and adding ad-hoc extensions that cannot be expressed by formalisms for efficient recognition of regular languages, such as deterministic finite automata. Parsing Expression Grammars are a formalism that can describe all deterministic context-free languages and has a simple computational model. In this paper, we present a formalization of regexes via transformation to Parsing Expression Grammars. The proposed transformation easily accommodates several of the common regex extensions, giving a formal meaning to them. It also provides a clear computational model that helps to estimate the efficiency of regex-based matchers, and a basis for specifying provably correct optimizations for them.
We introduce MORA, an automated tool for generating invariants of probabilistic programs. Inputs to MORA are so-called Prob-solvable loops, that is probabilistic programs with polynomial assignments over random variables and parametrized distributions. Combining methods from symbolic computation and statistics, MORA computes invariant properties over higher-order moments of loop variables, expressing, for example, statistical properties, such as expected values and variances, over the value distribution of loop variables.
Finitary Idealized Concurrent Algol (FICA) is a prototypical programming language combining functional, imperative, and concurrent computation. There exists a fully abstract game model of FICA, which in principle can be used to prove equivalence and safety of FICA programs. Unfortunately, the problems are undecidable for the whole language, and only very rudimentary decidable sub-languages are known. We propose leafy automata as a dedicated automata-theoretic formalism for representing the game semantics of FICA. The automata use an infinite alphabet with a tree structure. We show that the game semantics of any FICA term can be represented by traces of a leafy automaton. Conversely, the traces of any leafy automaton can be represented by a FICA term. Because of the close match with FICA, we view leafy automata as a promising starting point for finding decidable subclasses of the language and, more generally, to provide a new perspective on models of higher-order concurrent computation. Moreover, we identify a fragment of FICA that is amenable to verification by translation into a particular class of leafy automata. Using a locality property of the latter class, where communication between levels is restricted and every other level is bounded, we show that their emptiness problem is decidable by reduction to Petri net reachability.
We demonstrate a Bell state analyzer that operates directly on frequency mismatch. Based on electro-optic modulators and Fourier-transform pulse shapers, our quantum frequency processor design implements interleaved Hadamard gates in discrete frequency modes. Experimental tests on entangled-photon inputs reveal accuracies of $sim$98% for discriminating between the $|Psi^+rangle$ and $|Psi^-rangle$ frequency-bin Bell states. Our approach resolves the tension between wavelength-multiplexed state transport and high-fidelity Bell state measurements, which typically require spectral indistinguishability.
In this work we introduce a notion of independence based on finite-state automata: two infinite words are independent if no one helps to compress the other using one-to-one finite-state transducers with auxiliary input. We prove that, as expected, the set of independent pairs of infinite words has Lebesgue measure 1. We show that the join of two independent normal words is normal. However, the independence of two normal words is not guaranteed if we just require that their join is normal. To prove this we construct a normal word $x_1x_2x_3ldots$ where $x_{2n}=x_n$ for every $n$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
