Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 20 of 49 for “"pushdown automata"”.

  1. Deep Pushdown Automata and Their Restricted Versions

    Pro přirozené číslo n, n-expandovatelné hluboké zasobníkové automaty vždy obsahují maximálně n výskytů nevstupních symbolů v jejich zásobníku v průběhu jakékoli kompilace. Jako hlavní výsledek, tato práce demonstruje, že tyto automaty mají stejnou vyjadřovací sílu jako automaty s #, nacházející …

    brno-tech Repository record for Deep Pushdown Automata and Their Restricted Versions (opens in a new tab)

  2. On collapsible pushdown automata, their graphs and the power of links

    <p>Higher-Order Pushdown Automata (HOPDA) are abstract machines equipped with a nested stacks of stacks... of stacks of stacks. Collapsible pushdown automata (CPDA) enhance these stacks with the addition of ‘links’ emanating from atomic elements to the higher-order stacks below. For trees CPDA are …

    oxford Repository record for On collapsible pushdown automata, their graphs and the power of links (opens in a new tab)

  3. Weighted Logics and Weighted Simple Automata for Context-Free Languages of Infinite Words

    … between monadic second-order logic and finite automata for both finite and infinite words. This BET- Theorem has been extended by Lautemann, Schwentick and Thérien to context-free languages by introducing a monadic second-order logic with an additional existentially quantified second-order …

    qucosa-diss

  4. QUANTUM AND TRANSLUCENT PARADIGMS IN AUTOMATA THEORY: A STUDY ON COMPUTATIONAL CAPABILITIES

    Within the realm of automata theory, various models differ on their processing mechanisms and computational paradigms. This study investigates two computational paradigms, recently introduced in the literature: quantum and translucency. Specifically, we investigate Quantum Finite State Automata …

    milano Repository record for QUANTUM AND TRANSLUCENT PARADIGMS IN AUTOMATA THEORY: A STUDY ON COMPUTATIONAL CAPABILITIES (opens in a new tab)

  5. Programming Using Automata and Transducers

    Automata, the simplest model of computation, have proven to be an effective tool in reasoning about programs that operate over strings. Transducers augment automata to produce outputs and have been used to model string and tree transformations such as natural language translations. The success of …

    penn Repository record for Programming Using Automata and Transducers (opens in a new tab)

  6. Multi-weighted Automata Models and Quantitative Logics

    Recently, multi-priced timed automata have received much attention for real-time systems. These automata extend priced timed automata by featuring several price parameters. This permits to compute objectives like the optimal ratio between rewards and costs. Arising from the model of timed automata, …

    qucosa-diss

  7. Complexity Aspects of Stack Automata

    … infrastructure. Countless different variants of automata have been described in literature over the last hundred years. This dissertation focuses on stack automata: an automaton with a one-way read-only input tape, and a working memory which operates like the stack data structure, and can only be …

    sask Repository record for Complexity Aspects of Stack Automata (opens in a new tab)

  8. Visibly pushdown transducers for approximate validation of streaming XML

    Visibly Pushdown Languages (VPLs), recognized by Visibly Pushdown Automata (VPAs), are a nicely behaved family of context-free languages. It has been shown that VPAs are equivalent to Extended Document Type Definitions (EDTDs), and thus, they provide means for elegantly solving various problems on …

    uvic Repository record for Visibly pushdown transducers for approximate validation of streaming XML (opens in a new tab)

  9. FINGERPRINTING MALICIOUS IP TRAFFIC

    … upon k-means clustering, sequence mining and Pushdown Automata (PDAs) to capture the network behaviors of malware family groups. Indeed, the generated PDAs are actually network signatures for malware family groups. Our results show that the proposed malicious detection and attribution …

    concordia Download PDF for FINGERPRINTING MALICIOUS IP TRAFFIC (opens in a new tab)

  10. Fundamental techniques for the scalable analysis of systems

    … algorithm for a specific class of visibly pushdown automata.<br>The class is general, and the motivation for the class stems from its use in trace abstraction.<br>Trace abstraction is an approach to verify programs with procedures.<br>In this context, minimization is crucial to circumvent …

    freiburg-diss Repository record for Fundamental techniques for the scalable analysis of systems (opens in a new tab)

  11. English into Braille translation using augmented transition networks

    … Transition Networks, which are a development of pushdown automata. Its main advantage is that it offers great computational power which permits the representation of translation rules and their exceptions to these in a direct way. The translation program is written in PASCAL and uses a small …

    city-london Download PDF for English into Braille translation using augmented transition networks (opens in a new tab)

  12. Evaluating conjunctive and graph queries over the EL profile of OWL 2

    … encode the regular role inclusions using finite automata that can be worst-case exponential in size, and thus are not optimal. In our PSpace procedure, we address this problem by using a novel, succinct encoding of regular role inclusions based on pushdown automata with a bounded stack. Moreover, …

    oxford Repository record for Evaluating conjunctive and graph queries over the EL profile of OWL 2 (opens in a new tab)

  13. A formalisation of the theory of context-free languages in higher order logic

    … results involving context-free grammars and pushdown automata. These include but are not limited to the equivalence between those two formalisms, the normalisation of CFGs, and the pumping lemma for proving a language is not context-free. As an application of this theory, we describe the …

    anu Repository record for A formalisation of the theory of context-free languages in higher order logic (opens in a new tab)

  14. Automata methods and techniques for graph-structured data

    … A consistent theme of our work is the use of automata methods and techniques to process and reason about GSD. First, we address the problem of answering queries on GSD in a distributed environment. We focus on regular path queries (RPQs) – given by regular expressions matching paths in …

    uvic Repository record for Automata methods and techniques for graph-structured data (opens in a new tab)

  15. Saturation methods for global model-checking pushdown systems

    <p>Pushdown systems equip a finite state system with an unbounded stack memory, and are thus infinite state. By recording the call history on the stack, these systems provide a natural model for recursive procedure calls. Model-checking for pushdown systems has been well-studied. Tools implementing …

    oxford Repository record for Saturation methods for global model-checking pushdown systems (opens in a new tab)

  16. Game semantics based equivalence checking of higher-order programs

    … By representing strategies as Visibly Pushdown Automata (VPA) we show that observational equivalence of O-strict terms is decidable (and in fact is ExpTime-complete). We then consider extensions of the O-strict fragment. Adding general recursion or using most non-O-strict types leads to …

    oxford Repository record for Game semantics based equivalence checking of higher-order programs (opens in a new tab)

  17. Probabilistic verification beyond context-freeness

    … Recursive Markov Chains (RMCs) and Probabilistic Pushdown Automata (pPDAs). Recent advancements, including extensions to higher-order grammars like Probabilistic Higher-Order Recursion Schemes (PHORS), offer enhanced expressiveness but introduce significant challenges, such as the undecidability …

    oxford Repository record for Probabilistic verification beyond context-freeness (opens in a new tab)

  18. Modifikované hluboké zásobníkové automaty

    Tato práce představuje dvě nové modifikace hlubokých zásobníkových automatů - bezestavové hluboké zásobníkové automaty a paralelní bezestavové hluboké zásobníkové automaty.V teoretické části jsou zavedeny formální definice a také je zde zkoumána síla těchto automatů. V pratické části je ukázána na …

    brno-tech Repository record for Modifikované hluboké zásobníkové automaty (opens in a new tab)

  19. Nové verze zásobníkových automatů

    Táto diplomová práca sa zaoberá verziami viac-zásobníkových automatov založených na hlbokých zásobníkoch. Zavádza novú modifikáciu Vstupom riadený hlboký viac-zásobníkový automat, ktorý pozostáva z dvoch a viac hlbokých zásobníkov a aktuálny vstupný symbol určuje, či automat vykonáva operáciu push, …

    brno-tech Repository record for Nové verze zásobníkových automatů (opens in a new tab)

  20. Nové typy hlubokých zásobníkových automatů

    Tato bakalářská práce se zabývá novými typy hlubokých zásobníkových automatů. Stručně nastíní motivaci pro jejich zavedení, formálně je definuje a porovnává jejich vyjadřovací sílu s hlubokými zásobníkovými automaty. Dále jsou uvedeny příklady jazyků a jejich zpracování v zavedených modifikacích …

    brno-tech Repository record for Nové typy hlubokých zásobníkových automatů (opens in a new tab)

Page 1 of 3