1,721,000 research outputs found
Beyond operator-precedence grammars and languages
Full text linkOperator Precedence Languages (OPL) are deterministic context-free and have desirable properties. OPL are parallely parsable, and, when structurally compatible, are closed under Boolean operations, concatenation and star; they include the Input Driven languages. OPL use three relations between two terminal symbols, to assign syntax structure to words. We extend such relations to k-tuples of consecutive symbols, in agreement with strictly locally testable regular languages. For each k, the new corresponding class of Higher-order Operator Precedence languages properly includes the OPL and enjoy many of their properties. OPL are a strict hierarchy based on k, which contains maximal languages
A FIRST-ORDER COMPLETE TEMPORAL LOGIC FOR STRUCTURED CONTEXT-FREE LANGUAGES
Full text linkThe problem of model checking procedural programs has fostered much research towards the definition of temporal logics for reasoning on context-free structures. The most notable of such results are temporal logics on Nested Words, such as CaRet and NWTL. Recently, the logic OPTL was introduced, based on the class of Operator Precedence Languages (OPLs), more powerful than Nested Words. We define the new OPL-based logic POTL and prove its FO-completeness. POTL improves on NWTL by enabling the formulation of requirements involving pre/post-conditions, stack inspection, and others in the presence of exception-like constructs. It improves on OPTL too, which instead we show not to be FO-complete; it also allows to express more easily stack inspection and function-local properties. In a companion paper we report a model checking procedure for POTL and experimental results based on a prototype tool developed therefor. For completeness a short summary of this complementary result is provided in this paper too
Operator precedence temporal logic and model checking
Full text linkIn the last decades much research effort has been devoted to extending the success of model checking from the traditional field of finite state machines and various versions of temporal logics to suitable subclasses of context-free languages and appropriate extensions of temporal logics. To the best of our knowledge such attempts only covered structured languages, i.e. languages whose structure is immediately “visible” in their sentences, such as tree-languages or visibly pushdown ones. In this paper we present a new temporal logic suitable to express and automatically verify properties of operator precedence languages. This “historical” language family has been recently proved to enjoy fundamental algebraic and logic properties that make it suitable for model checking applications yet breaking the barrier of visible-structure languages (in fact the original motivation of its inventor Floyd was just to support efficient parsing, i.e. building the “hidden syntax tree” of language sentences). We prove that our logic is at least as expressive as analogous logics defined for visible pushdown languages yet covering a much more powerful family; we design a procedure that, given a formula in our logic builds an automaton recognizing the sentences satisfying the formula, whose size is at most exponential in the length of the formula. Our results cover both finite and infinite string languages
Static Analysis of Infrastructure as Code: A Survey
Full text linkThe increasing use of Infrastructure as Code (IaC) in DevOps leads to benefits in speed and reliability of deployment operation, but extends to infrastructure challenges typical of software systems. IaC scripts can contain defects that result in security and reliability issues in the deployed infrastructure: Techniques for detecting and preventing them are needed. We analyze and survey the current state of research in this respect by conducting a literature review on static analysis techniques for IaC. We describe analysis techniques, defect categories and platforms targeted by tools in the literature
APERIODICITY, STAR-FREENESS, AND FIRST-ORDER LOGIC DEFINABILITY OF OPERATOR PRECEDENCE LANGUAGES
Full text linkA classic result in formal language theory is the equivalence among non-counting, or aperiodic, regular languages, and languages defined through star-free regular expressions, or first-order logic. Past attempts to extend this result beyond the realm of regular languages have met with difficulties: for instance it is known that star-free tree languages may violate the non-counting property and there are aperiodic tree languages that cannot be defined through first-order logic. We extend such classic equivalence results to a significant family of deterministic context-free languages, the operator-precedence languages (OPL), which strictly includes the widely investigated visibly pushdown, alias input-driven, family and other structured context-free languages. The OP model originated in the ’60s for defining programming languages and is still used by high performance compilers; its rich algebraic properties have been investigated initially in connection with grammar learning and recently completed with further closure properties and with monadic second order logic definition. We introduce an extension of regular expressions, the OP-expressions (OPE) which define the OPLs and, under the star-free hypothesis, define first-order definable and non-counting OPLs. Then, we prove, through a fairly articulated grammar transformation, that aperiodic OPLs are first-order definable. Thus, the classic equivalence of star-freeness, aperiodicity, and first-order definability is established for the large and powerful class of OPLs. We argue that the same approach can be exploited to obtain analogous results for visibly pushdown languages too
Verification of Programs with Exceptions Through Operator Precedence Automata
Full text linkOperator Precedence Languages are one of the most expressive classes of context-free languages that enable Model Checking. Recently, the First-Order complete Precedence Oriented Temporal Logic (POTL) has been introduced for expressing properties on models defined through Operator Precedence Automata (OPA), a variant of Pushdown Automata for OPLs; moreover, an efficient tool called Precedence Oriented Model Checker (POMC) was devised for POTL. We propose here the core algorithms of POMC for on-the-fly depth-first exploration of the search space: for OPA, a reachability algorithm; for their ω -word variant, a fair-cycle detection algorithm. We have refined the tool with a user-friendly DSL called MiniProc for expressing procedural code with exceptions. We show how the expressiveness of POMC can be used to verify programs which make use of exceptions, thus overcoming the limits of LTL-based Model Checking. We demonstrate the effectiveness of POMC through a case study
Linear temporal logics for structured context-free languages
Full text linkThe need to extend traditional temporal logics to express and prove properties typical of stack-based formalisms led, among others, to CaRet and NWTL on Visibly Pushdown Languages (VPL). Such formalisms support, e.g., model checking of procedural programs and other context-free languages (CFL). To further and significantly extend their expressive power, we recently introduced the logic OPTL, based on Operator Precedence Languages (OPL) which cover a much wider subclass of CFL. In this communication we survey the latest developments of our work. We introduced a novel temporal logic, POTL, that redefines OPTL to be First-Order complete. Furthermore, POTL's semantics is better connected to the typical tree-structure of CFL while retaining the ability to reason about linear time. Besides the theoretical advancements, we are also moving steps toward the implementation of POTL model checking
Star-Freeness, First-Order Definability and Aperiodicity of Structured Context-Free Languages
Full text linkA classic result in formal language theory is the equivalence among aperiodic finite automata, star-free regular expressions, and first-order logic on words. Extending these results to structured subclasses of context-free languages, such as tree languages, did not work as smoothly: there are star-free tree languages that are counting. We argue that investigating the same properties within the family of operator precedence languages (OPLs) by going back to string languages rather than tree languages may lead to equivalences that perfectly match those on regular languages. We define operator precedence expressions; we show that they define exactly the class of OPLs and that, when restricted to the star-free subclass, coincide with first-order definable OPLs and are aperiodic. Since operator precedence languages strictly include other classes of structured languages such as visibly pushdown languages, the same results given in this paper hold as trivial corollary for that family too
Weighted operator precedence languages
Full text linkIn the last years renewed investigation of operator precedence languages (OPL) led to discover important properties thereof: OPL are closed with respect to all major operations, are characterized, besides by the original grammar family, in terms of an automata family (OPA) and an MSO logic; furthermore they significantly generalize the well-known visibly pushdown languages (VPL). A different area of research investigates quantitative evaluations of formal languages by adding weights to strings. In this paper, we lay the foundation to marry these two research fields. We introduce weighted operator precedence automata and show how they are both strict extensions of OPA and weighted visibly pushdown automata. We prove a Nivat-like result which shows that quantitative OPL can be described by unweighted OPA and very particular weighted OPA. In a Büchi-like theorem, we show that weighted OPA are expressively equivalent to a weighted MSO-logic for OPL
- …
