Search

Your search keyword '"Pushdown automaton"' showing total 1,590 results
Start Over Descriptor "Pushdown automaton"

Refine your results

1,590 results on '"Pushdown automaton"'

1. Quantum Representation for Deterministic Push-Down Automata.

Author

Puram, Varun teja, George, K. M., and Thomas, Johnson P.

Subjects
BOOLEAN matrices, QUANTUM computing, BOOLEAN functions, FINITE state machines, ROBOTS
Abstract

There are many papers presenting quantum computing models. The definitions parallel the classical definitions of finite state automata, push-down automata, context-free grammars, etc. Classical computing model definitions define languages precisely. We can state that a string belongs to a language or does not belong to it with no room for error. Quantum definitions do not possess this certainty. Sacrificing the certainty and adopting a quantum definition of a computing model does not appear to provide any concrete power to the model. Therefore, the path of this paper is to begin from the classical definition and end in a quantum circuit. In this paper, we start from a deterministic push-down automaton (DPDA). We present circuits for state transition and stack operations. The circuits presented can be viewed as independent algorithms. As an example, the approach used to construct the circuit for state transition can be utilized to build the circuit for a function presented as a Boolean matrix. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

2. Sequential Value Passing Yields a Kleene Theorem for Processes

Author

Baeten, Jos C. M., Luttik, Bas, Goos, Gerhard, Series Editor, Hartmanis, Juris, Founding Editor, van Leeuwen, Jan, Series Editor, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Kobsa, Alfred, Series Editor, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Nierstrasz, Oscar, Series Editor, Pandu Rangan, C., Editorial Board Member, Sudan, Madhu, Series Editor, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Weikum, Gerhard, Series Editor, Vardi, Moshe Y, Series Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Capretta, Venanzio, editor, Krebbers, Robbert, editor, and Wiedijk, Freek, editor

Published
2024
Full Text
View/download PDF

4. A Survey on Automata with Translucent Letters

Author

Otto, Friedrich, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, and Nagy, Benedek, editor

Published
2023
Full Text
View/download PDF

5. PUSHDOWN AUTOMATA AND CONTEXT-FREE GRAMMARS IN BISIMULATION SEMANTICS.

Author

BAETEN, JOS C. M., CARISSIMO, CESARE, and LUTTIK, BAS

Subjects
TURING machines, COMPOSITION operators, BISIMULATION, PHILOSOPHY of language, EQUIVALENCE (Linguistics)
Abstract

The Turing machine models an old-fashioned computer, that does not interact with the user or with other computers, and only does batch processing. Therefore, we came up with a Reactive Turing Machine that does not have these shortcomings. In the Reactive Turing Machine, transitions have labels to give a notion of interactivity. In the resulting process graph, we use bisimilarity instead of language equivalence. Subsequently, we considered other classical theorems and notions from automata theory and formal languages theory. In this paper, we consider the classical theorem of the correspondence between pushdown automata and context-free grammars. By changing the process operator of sequential composition to a sequencing operator with intermediate acceptance, we get a better correspondence in our setting. We find that the missing ingredient to recover the full correspondence is the addition of a notion of state awareness. [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

6. Backwards-reachability for cooperating multi-pushdown systems.

Author

Köcher, Chris and Kuske, Dietrich

Subjects
*POLYNOMIAL time algorithms, *ROBOTS
Abstract

A cooperating multi-pushdown system consists of a tuple of pushdown systems that can delegate the execution of recursive procedures to sub-tuples; control returns to the calling tuple once all sub-tuples finished their task. This allows the concurrent execution since disjoint sub-tuples can perform their task independently. Because of the concrete form of recursive descent into sub-tuples, the content of the multi-pushdown does not form an arbitrary tuple of words, but can be understood as a Mazurkiewicz trace. For such systems, we prove that the backwards reachability relation efficiently preserves recognizability, generalizing a result and proof technique by Bouajjani et al. for single-pushdown systems. It follows that the reachability relation is decidable for cooperating multi-pushdown systems in polynomial time and the same holds, e.g., for safety and liveness properties given by recognizable sets of configurations. [ABSTRACT FROM AUTHOR]

Published
2025
Full Text
View/download PDF

7. Sequential Value Passing Yields a Kleene Theorem for Processes

Author

Baeten, J.C.M. (Jos), Luttik, S.P. (Bas), Baeten, J.C.M. (Jos), and Luttik, S.P. (Bas)

Abstract

Communication with value passing has received ample attention in process theory. Value passing through a sequential composition has received much less attention. In recent work, we found that sequential value passing is the essential ingredient to prove the analogue of the classical theorem of the equivalence of pushdown automata and context-free grammars in a setting of interactive processes and bisimulation. Subsequently, we found that the treatment of sequential value passing in the process setting can be simplified considerably. We report on this simplification here, and find another application of sequential value passing, viz. a Kleene theorem for processes.

Published
2024
Full Text
View/download PDF

8. GoDetector: Detecting Concurrent Bug in Go

Author

Dongwen Zhang, Penghao Qi, and Yang Zhang

Subjects
Concurrency bugs, channel, WaitGroup, static analysis, pushdown automaton, Electrical engineering. Electronics. Nuclear engineering, TK1-9971
Abstract

Go provides a new concurrency mechanism based on message-passing, which brings a series of new concurrency bugs. The existing tools are highly dependent on model-checking methods in which they take the source program as the input of model-checking tools to detect the potential concurrent bugs. However, these methods can only qualitatively obtain the concurrency of the program but not obtain the exact number of concurrency bugs in the program. Meanwhile, these approaches are not sensitive to dead codes, which are prone to false negatives. Furthermore, few works have been done on detecting WaitGroup-related bugs in Go concurrent programming, which may cause deadlock. To this end, this paper proposes a novel approach GoDetector to detect concurrent bugs. GoDetector uses a detecting algorithm and a pushdown automaton to verify the channel-related concurrent bugs and WaitGroup-related concurrent bugs separately. To support the evaluation of the tool, 30 benchmarks are collected from the existing tools. GoDetector reports 2 channel safety errors, 29 deadlocks, and 11 WaitGroup-related errors. Compared with the existing tool Godel, GoDetector has the capacity to report more concurrency bugs and fewer false positives. GoDetector also offers additional support for the detection of WaitGroup variables. The experimental results indicate that GoDetector is more efficient at detecting the concurrency in regards to accuracy and diversity.

Published
2021
Full Text
View/download PDF

9. Generalized fuzzy automata with semantic computing.

Author

Wei, Lina, Huang, Guangjian, Wasti, Shahbaz Hassan, Hussain, Muhammad Jawad, and Jiang, Yuncheng

Subjects
*SEMANTIC computing, *FINITE state machines, *WEATHER forecasting, *ROBOTS
Abstract

Researches about semantic computing are usually evaluated by experiments, lacking support from the theory of computation. But traditional finite automata are defined on a fixed finite set of states. They will be invalid when a different application needs to change the states. However, semantic computing always asks for more robust automata that can modify itself according to the changes of states. Therefore, in this paper, we redefine traditional automata in more robust forms by semantic computing. The intuitive idea is when the state which an automaton is supposed to enter has changed, we drive automata into a state that is similar to the original one. We can find another similar state in the original state set to replace the changed state by semantic similarity. Based on the theories of semantic similarity, there always exists a similar state. Therefore, once a state has changed, we can always find a similar state to replace it, which means that we can empower automata to adapt to the changes of states. Our new automata bridge the gap between semantic computing and the theory of computation. Furthermore, we also redefine fuzzy finite automata and pushdown automata in more robust forms. Finally, we provide an application about the weather forecast, which indicates how to overcome the limitations of traditional automata. [ABSTRACT FROM AUTHOR]

Published
2021
Full Text
View/download PDF

10. On Termination and Boundedness of Nested Updatable Timed Automata

Author

Wang, Yuwei, Tao, Xiuting, Li, Guoqiang, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Liu, Shaoying, editor, Duan, Zhenhua, editor, Tian, Cong, editor, and Nagoya, Fumiko, editor

Published
2017
Full Text
View/download PDF

11. Contextual Approximation and Higher-Order Procedures

Author

Lazić, Ranko, Murawski, Andrzej S., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Jacobs, Bart, editor, and Löding, Christof, editor

Published
2016
Full Text
View/download PDF

12. Projection for Nested Word Automata Speeds up XPath Evaluation on XML Streams

Author

Sebastian, Tom, Niehren, Joachim, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Freivalds, Rūsiņš Mārtiņš, editor, Engels, Gregor, editor, and Catania, Barbara, editor

Published
2016
Full Text
View/download PDF

13. Regular Symmetry Patterns

Author

Lin, Anthony W., Nguyen, Truong Khanh, Rümmer, Philipp, Sun, Jun, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Jobstmann, Barbara, editor, and Leino, K. Rustan M., editor

Published
2016
Full Text
View/download PDF

14. Turing Machines with Shortcuts: Efficient Attribute-Based Encryption for Bounded Functions

Author

Boyen, Xavier, Li, Qinyi, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Josef, Kittler, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Manulis, Mark, editor, Sadeghi, Ahmad-Reza, editor, and Schneider, Steve, editor

Published
2016
Full Text
View/download PDF

15. Colored Nested Words

Author

Alur, Rajeev, Fisman, Dana, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Dediu, Adrian-Horia, editor, Janoušek, Jan, editor, Martín-Vide, Carlos, editor, and Truthe, Bianca, editor

Published
2016
Full Text
View/download PDF

16. Pushdown Automata and Context-Free Grammars in Bisimulation Semantics

Author

Baeten, Jos C.M., Carissimo, Cesare, Luttik, Bas, Baeten, Jos C.M., Carissimo, Cesare, and Luttik, Bas

Abstract

The Turing machine models an old-fashioned computer, that does not interact with the user or with other computers, and only does batch processing. Therefore, we came up with a Reactive Turing Machine that does not have these shortcomings. In the Reactive Turing Machine, transitions have labels to give a notion of interactivity. In the resulting process graph, we use bisimilarity instead of language equivalence. Subsequently, we considered other classical theorems and notions from automata theory and formal languages theory. In this paper, we consider the classical theorem of the correspondence between pushdown automata and context-free grammars. By changing the process operator of sequential composition to a sequencing operator with intermediate acceptance, we get a better correspondence in our setting. We find that the missing ingredient to recover the full correspondence is the addition of a notion of state awareness.

Published
2023

17. Pushdown automata and context-free grammars in bisimulation semantics

Author

Baeten, J.C.M. (Jos), Carissimo, C. (Cesare), Luttik, S.P. (Bas), Baeten, J.C.M. (Jos), Carissimo, C. (Cesare), and Luttik, S.P. (Bas)

Abstract

The Turing machine models an old-fashioned computer, that does not interact with the user or with other computers, and only does batch processing. Therefore, we came up with a Reactive Turing Machine that does not have these shortcomings. In the Reactive Turing Machine, transitions have labels to give a notion of interactivity. In the resulting process graph, we use bisimilarity instead of language equivalence. Subsequently, we considered other classical theorems and notions from automata theory and formal languages theory. In this paper, we consider the classical theorem of the correspondence between pushdown automata and context-free grammars. By changing the process operator of sequential composition to a sequencing operator with intermediate acceptance, we get a better correspondence in our setting. We find that the missing ingredient to recover the full correspondence is the addition of a notion of state awareness.

Published
2023
Full Text
View/download PDF

18. Synchronized Recursive Timed Automata

Author

Uezato, Yuya, Minamide, Yasuhiko, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Davis, Martin, editor, Fehnker, Ansgar, editor, McIver, Annabelle, editor, and Voronkov, Andrei, editor

Published
2015
Full Text
View/download PDF

19. Visibly Counter Languages and the Structure of

Author

Hahn, Michael, Krebs, Andreas, Lange, Klaus-Jörn, Ludwig, Michael, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Italiano, Giuseppe F., editor, Pighizzini, Giovanni, editor, and Sannella, Donald T., editor

Published
2015
Full Text
View/download PDF

20. A Chomsky-Schützenberger Theorem for Weighted Automata with Storage

Author

Herrmann, Luisa, Vogler, Heiko, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Maletti, Andreas, editor

Published
2015
Full Text
View/download PDF

21. Model Checking Parameterized Asynchronous Shared-Memory Systems

Author

Durand-Gasselin, Antoine, Esparza, Javier, Ganty, Pierre, Majumdar, Rupak, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Kroening, Daniel, editor, and Păsăreanu, Corina S., editor

Published
2015
Full Text
View/download PDF

22. Periodic properties of pushdown automata.

Author

Ivanov, Ilya E.

Subjects
*MACHINE theory, *FINITE state machines
Abstract

Finite automata transform periodic sequences into periodic ones. The period of the output sequence is bounded from above by a linear function of input period. It is known that pushdown automata also preserve the set of periodic sequences. We prove that the output period for one-counter pushdown automata is bounded from above by a quadratic function of input period. We also give an example of an automaton with a quadratic lower bound on output period. [ABSTRACT FROM AUTHOR]

Published
2019
Full Text
View/download PDF

23. The Triple-Pair Construction for Weighted ω-Pushdown Automata

Author

Zoltán Ésik, Werner Kuich, and Manfred Droste

Subjects
Discrete mathematics, lcsh:Mathematics, Computer Science::Information Retrieval, 010102 general mathematics, Mathematics::Rings and Algebras, Pushdown automaton, Astrophysics::Instrumentation and Methods for Astrophysics, Computer Science - Formal Languages and Automata Theory, Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), 0102 computer and information sciences, lcsh:QA1-939, 01 natural sciences, lcsh:QA75.5-76.95, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, 010201 computation theory & mathematics, F.4.3, ComputingMethodologies_DOCUMENTANDTEXTPROCESSING, Computer Science (miscellaneous), Computer Science::General Literature, lcsh:Electronic computers. Computer science, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Computer Science::Formal Languages and Automata Theory, Mathematics
Abstract

Let S be a complete star-omega semiring and Sigma be an alphabet. For a weighted omega-pushdown automaton P with stateset 1...n, n greater or equal to 1, we show that there exists a mixed algebraic system over a complete semiring-semimodule pair ((S<>)^nxn, (S<>)^n) such that the behavior ||P|| of P is a component of a solution of this system. In case the basic semiring is the Boolean semiring or the semiring of natural numbers (augmented with infinity), we show that there exists a mixed context-free grammar that generates ||P||. The construction of the mixed context-free grammar from P is a generalization of the well known triple construction and is called now triple-pair construction for omega-pushdown automata., Comment: In Proceedings AFL 2017, arXiv:1708.06226. The article was prepared as a joint work with the late Zolt\'an \'Esik (1951-2016) whose definite intention was to publish the results

Published
2022
Full Text
View/download PDF

24. TkT: Automatic Inference of Timed and Extended Pushdown Automata

Author

Fabrizio Pastore, Leonardo Mariani, Michell Guzman, Daniela Micucci, Pastore, F, Micucci, D, Guzman, M, and Mariani, L

Subjects
Performance analysi, Computer science, 02 engineering and technology, computer.software_genre, Dynamic analysi, ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI, Automata, Trace analysi, 0202 electrical engineering, electronic engineering, information engineering, Timing, Software system, Timed automata, Software systems, Data mining, Clocks, Computer science [C05] [Engineering, computing & technology], Programming language, Pushdown automaton, INF/01 - INFORMATICA, Computational modeling, 020207 software engineering, Sciences informatiques [C05] [Ingénierie, informatique & technologie], Automaton, Specification mining, Automatic inference, Model inference, computer, Software
Abstract

To mitigate the cost of manually producing and maintaining models capturing software specifications,specification miningtechniques can be exploited to automatically derive up-to-date models that faithfully represent the behavior of software systems. So far,specification mining solutions focused on extracting information about the functional behavior of the system, especially in the form ofmodels that represent the ordering of the operations. Well-known examples are finite state models capturing the usage protocol ofsoftware interfaces and temporal rules specifying relations among system events.Although the functional behavior of a software system is a primary aspect of concern, there are several other non-functionalcharacteristics that must be typically addressed jointly with the functional behavior of a software system. Efficiency is one of the most relevant characteristics. Indeed, an application that delivers the right functionalities with an inefficient implementation may fail to satisfy the expectations of its users.Interestingly, the timing behavioris strongly dependent on the functional behavior of a software system. For instance, the timing of an operation depends on the functional complexity and size of the computation that is performed. Consequently, models that combine the functional and timing behaviors, as well as their dependencies, are extremely important to precisely reason on the behavior of software systems.In this paper, we address the challenge of generating models that capture both the functional and timing behavior of a software system from execution traces. The result is the Timed k-Tail (TkT) specification mining technique, which can mine finite state models that capture such an interplay: the functional behavior is represented by the possible order of the events accepted by the transitions, while the timing behavior is represented through clocks and clock constraints of different nature associated with transitions.Our empirical evaluation with several libraries and applications shows that TkT can generate accurate models, capable of supporting the identification of timing anomalies due to overloaded environment and performance faults. Furthermore, our study shows that TkT outperforms state-of-the-art techniques in terms of scalability and accuracy of the mined models.

Published
2022
Full Text
View/download PDF

25. Not All Multi-Valued Partial CFL Functions Are Refined by Single-Valued Functions (Extended Abstract)

Author

Yamakami, Tomoyuki, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Diaz, Josep, editor, Lanese, Ivan, editor, and Sangiorgi, Davide, editor

Published
2014
Full Text
View/download PDF

26. Reachability in Pushdown Register Automata

Author

Murawski, Andrzej S., Ramsay, Steven J., Tzevelekos, Nikos, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Csuhaj-Varjú, Erzsébet, editor, Dietzfelbinger, Martin, editor, and Ésik, Zoltán, editor

Published
2014
Full Text
View/download PDF

27. Monoid Automata for Displacement Context-Free Languages

Author

Sorokin, Alexey, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Colinet, Margot, editor, Katrenko, Sophia, editor, and Rendsvig, Rasmus K., editor

Published
2014
Full Text
View/download PDF

28. Unary Pushdown Automata and Straight-Line Programs

Author

Chistikov, Dmitry, Majumdar, Rupak, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Esparza, Javier, editor, Fraigniaud, Pierre, editor, Husfeldt, Thore, editor, and Koutsoupias, Elias, editor

Published
2014
Full Text
View/download PDF

29. On Decidability and Closure Properties of Language Classes with Respect to Bio-operations

Author

Ibarra, Oscar H., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Murata, Satoshi, editor, and Kobayashi, Satoshi, editor

Published
2014
Full Text
View/download PDF

30. Boundary Sets of Regular and Context-Free Languages

Author

Holzer, Markus, Jakobi, Sebastian, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Jürgensen, Helmut, editor, Karhumäki, Juhani, editor, and Okhotin, Alexander, editor

Published
2014
Full Text
View/download PDF

31. A Note on Pushdown Automata Systems

Author

Petersen, Holger, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Jürgensen, Helmut, editor, Karhumäki, Juhani, editor, and Okhotin, Alexander, editor

Published
2014
Full Text
View/download PDF

32. Automata with Reversal-Bounded Counters: A Survey

Author

Ibarra, Oscar H., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Jürgensen, Helmut, editor, Karhumäki, Juhani, editor, and Okhotin, Alexander, editor

Published
2014
Full Text
View/download PDF

33. Visibly Pushdown Transducers with Well-Nested Outputs

Author

Reynier, Pierre-Alain, Talbot, Jean-Marc, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Shur, Arseny M., editor, and Volkov, Mikhail V., editor

Published
2014
Full Text
View/download PDF

34. How Many Ants Does It Take to Find the Food?

Author

Emek, Yuval, Langner, Tobias, Stolz, David, Uitto, Jara, Wattenhofer, Roger, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, and Halldórsson, Magnús M., editor

Published
2014
Full Text
View/download PDF

35. Well-Structured Pushdown System: Case of Dense Timed Pushdown Automata

Author

Cai, Xiaojuan, Ogawa, Mizuhito, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Codish, Michael, editor, and Sumii, Eijiro, editor

Published
2014
Full Text
View/download PDF

36. First-Order Logic on CPDA Graphs

Author

Parys, Paweł, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Hirsch, Edward A., editor, Kuznetsov, Sergei O., editor, Pin, Jean-Éric, editor, and Vereshchagin, Nikolay K., editor

Published
2014
Full Text
View/download PDF

37. Oracle Pushdown Automata, Nondeterministic Reducibilities, and the Hierarchy over the Family of Context-Free Languages

Author

Yamakami, Tomoyuki, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Geffert, Viliam, editor, Preneel, Bart, editor, Rovan, Branislav, editor, Štuller, Július, editor, and Tjoa, A Min, editor

Published
2014
Full Text
View/download PDF

38. Impartiality and Anticipation for Monitoring of Visibly Context-Free Properties

Author

Decker, Normann, Leucker, Martin, Thoma, Daniel, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Legay, Axel, editor, and Bensalem, Saddek, editor

Published
2013
Full Text
View/download PDF

39. Trimming Visibly Pushdown Automata

Author

Caralp, Mathieu, Reynier, Pierre-Alain, Talbot, Jean-Marc, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Konstantinidis, Stavros, editor

Published
2013
Full Text
View/download PDF

40. Decidability and Enumeration for Automatic Sequences: A Survey

Author

Shallit, Jeffrey, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Bulatov, Andrei A., editor, and Shur, Arseny M., editor

Published
2013
Full Text
View/download PDF

42. Modal Process Rewrite Systems

Author

Beneš, Nikola, Křetínský, Jan, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Roychoudhury, Abhik, editor, and D’Souza, Meenakshi, editor

Published
2012
Full Text
View/download PDF

43. Strictness of the Collapsible Pushdown Hierarchy

Author

Kartzow, Alexander, Parys, Paweł, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Rovan, Branislav, editor, Sassone, Vladimiro, editor, and Widmayer, Peter, editor

Published
2012
Full Text
View/download PDF

44. Event Clock Automata: From Theory to Practice

Author

Geeraerts, Gilles, Raskin, Jean-François, Sznajder, Nathalie, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Fahrenberg, Uli, editor, and Tripakis, Stavros, editor

Published
2011
Full Text
View/download PDF

45. Language Equivalence of Deterministic Real-Time One-Counter Automata Is NL-Complete

Author

Böhm, Stanislav, Göller, Stefan, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Murlak, Filip, editor, and Sankowski, Piotr, editor

Published
2011
Full Text
View/download PDF

46. Tree Template Matching in Ranked Ordered Trees by Pushdown Automata

Author

Flouri, Tomáš, Janoušek, Jan, Melichar, Bořivoj, Iliopoulos, Costas S., Pissis, Solon P., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Bouchou-Markhoff, Béatrice, editor, Caron, Pascal, editor, Champarnaud, Jean-Marc, editor, and Maurel, Denis, editor

Published
2011
Full Text
View/download PDF

47. LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata

Author

Aizikowitz, Tamar, Kaminski, Michael, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Kulikov, Alexander, editor, and Vereshchagin, Nikolay, editor

Published
2011
Full Text
View/download PDF

48. Diagnosability of Pushdown Systems

Author

Morvan, Christophe, Pinchinat, Sophie, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Namjoshi, Kedar, editor, Zeller, Andreas, editor, and Ziv, Avi, editor

Published
2011
Full Text
View/download PDF

49. An Automata-Theoretical Characterization of Context-Free Trace Languages

Author

Nagy, Benedek, Otto, Friedrich, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Černá, Ivana, editor, Gyimóthy, Tibor, editor, Hromkovič, Juraj, editor, Jefferey, Keith, editor, Králović, Rastislav, editor, Vukolić, Marko, editor, and Wolf, Stefan, editor

Published
2011
Full Text
View/download PDF

50. A Note on a Tree-Based 2D Indexing

Author

Žd’árek, Jan, Melichar, Bořivoj, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Domaratzki, Michael, editor, and Salomaa, Kai, editor

Published
2011
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results