Search

A decidability proof for bisimulation equivalence of first-order grammars is given. It is an alternative proof for a result by S\'enizergues (1998, 2005) that subsumes his affirmative solution of the famous decidability question for deterministic pushdown automata. The presented proof is conceptually simpler, and a particular novelty is that it is not given as two semidecision procedures but it provides an explicit algorithm that might be amenable to a complexity analysis., Comment: version accepted to JCSS

International audience; — We consider the complexity of integer base expansions of algebraic irrational numbers from a computational point of view. We show that the Hartmanis–Stearns problem can be solved in a satisfactory way for the class of multistack machines. In this direction, our main result is that the base-b expansion of an algebraic irrational real number cannot be generated by a deterministic pushdown automaton. We also confirm an old claim of Cobham proving that such numbers cannot be generated by a tag machine with dilation factor larger than one.

Edit distance l-neighbourhood of a formal language is the set of all strings that can be transformed to one of the strings in this language by at most l insertions and deletions. Both the regular and the context-free languages are known to be closed under this operation, whereas the family recognized by deterministic pushdown automata is not. This paper establishes the closure of the family recognized by input-driven pushdown automata (IDPDA), also known as visibly pushdown automata, under the edit distance neighbourhood operation. For an n-state nondeterministic IDPDA with n stack symbols, an automaton for its edit distance l-neighbourhood using O ( n l + 1 ) states is constructed, and an asymptotically matching lower bound is established. For an n-state deterministic IDPDA, its 1-neighbourhood in the worst case requires a deterministic IDPDA with at least 2 Ω ( n 2 ) states.

In this paper, we study the model checking problem of pushdown systems for projection temporal logic (PTL), an interval-based temporal logic that is as expressive as the full regular languages. For this, we provide an algorithm to decide whether a pushdown system, determined by a pushdown automaton, satisfies a desired logic property, by using relevant automata notations and operations. The algorithm terminates in exponential time for normal PTL properties, i.e. properties specified as normal PTL formulas. To show the lower bound of complexity of the model checking problem, we also construct a polynomial-time reduction from the acceptance problem of a linearly bounded alternating Turing machine. As a result, the model checking problem of pushdown systems for normal PTL properties is EXPTIME-complete.

Let G be a group and let φ : Σ ⁎ → G be a monoid homomorphism from the set of all strings Σ ⁎ over some finite alphabet Σ onto the group G. The set Σ is then called a generating set for G and the language { 1 } φ − 1 ⊆ Σ ⁎ is called the word problem of G with respect to the generating set Σ (via the homomorphism φ) and is denoted by W ( G , Σ ) . We consider nine conditions that hold in each such language of the form W ( G , Σ ) and determine which combinations of these conditions are equivalent to the property of the language in question being the word problem of a group. We show that each of these nine conditions is decidable for the family of regular languages but that each is undecidable for the family of one-counter languages (the languages accepted by one-counter pushdown automata). We also show that the property of a language being the word problem of a group is undecidable for the family of one-counter languages but is decidable for the family of deterministic context-free languages (the languages accepted by deterministic pushdown automata).

Several kinds of quantum pushdown automata models have been proposed, and their computational power has been investigated intensively. However, for some quantum pushdown automaton models, it is unknown whether quantum models are at least as powerful as their classical counterparts or not. This is due to the reversibility restriction. In this paper, we introduce a new quantum pushdown automaton model that has a garbage tape. This model can overcome the reversibility restriction by exploiting the garbage tape to store popped symbols. We show that the proposed model can simulate any quantum pushdown automaton with classical stack as well as any probabilistic pushdown automaton. We also show that our model can solve a certain promise problem exactly while deterministic pushdown automata cannot. These results imply that our model is strictly more powerful than its classical counterparts in the setting of exact, one-sided error and non-deterministic computation. Showing impossibility for a promise problem is a difficult task in general. However, by analyzing the behavior of a deterministic pushdown automaton carefully, we obtained the impossibility result. This is one of the main contributions of the paper.

We study the size-cost of Boolean operations on constant height nondeterministic pushdown automata, i.e. on pushdown automata with a constant limit on the size of the pushdown. For intersection, we show an exponential simulation and prove that the exponential blow-up is necessary. For union, instead, we provide a linear trade-off while, for complement, we show a double-exponential simulation and prove a single-exponential lower bound.

Two-player games on graphs are central in many problems in formal verification and program analysis, such as synthesis and verification of open systems. In this work, we consider solving recursive game graphs (or pushdown game graphs) that model the control flow of sequential programs with recursion. While pushdown games have been studied before with qualitative objectives—such as reachability and ω-regular objectives—in this work, we study for the first time such games with the most well-studied quantitative objective, the mean-payoff objective. In pushdown games, two types of strategies are relevant: (1) global strategies, which depend on the entire global history; and (2) modular strategies, which have only local memory and thus do not depend on the context of invocation but rather only on the history of the current invocation of the module. Our main results are as follows: (1) One-player pushdown games with mean-payoff objectives under global strategies are decidable in polynomial time. (2) Two-player pushdown games with mean-payoff objectives under global strategies are undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies are NP-hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies are NP-complete). We also establish the optimal strategy complexity by showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games and memoryless modular strategies are sufficient in two-player pushdown games. Finally, we also show that all the problems have the same complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded.

This paper introduces the concepts of fuzzy tree pushdown automata and fuzzy context-free tree grammars. At first, we show that any fuzzy context-free tree grammar can be converted into a corresponding definition of fuzzy Chomsky normal form for trees. Then, the relation between a fuzzy context-free tree grammar and a fuzzy tree pushdown automaton is investigated. In fact, we show that the class of languages accepted by fuzzy tree pushdown automata is identical to the one generated by fuzzy context-free tree grammars. Some examples are given to clarify the results.

The following problem is shown undecidable: given regular languages L,K of finite trees, decide if there exists a deterministic tree-walking automaton which accepts all trees in L and rejects all trees in K. The proof uses a technique of Kopczy\'nski from LICS 2016.

We shall consider nondeterministic and deterministic automata equipped with a limited pushdown (constant height npda s and dpda s) as well as their two-way versions (constant height 2 npda s and 2 dpda s). We show two double-exponential gaps for these devices, namely, (i) for complementing constant height one-way npda s and (ii) for converting constant height 2 npda s or 2 dpda s into one-way devices.

We propose in this paper a model checking framework for service trust behaviors. We devise a new trust behavior model, which is a deterministic PushDown Automaton (PDA) based trust behavior model. This model is built based on the observations' sequences, which are derived from the interactions with services. Furthermore, we express the regular and non-regular trust behavior properties using Fixed point Logic with Chop (FLC). The model checking of service trust behaviors with respect to trust properties is performed using a symbolic FLC model checking algorithm. Finally, we present some experiments to assess the efficiency of the proposed algorithm.

We investigate the determinacy strength of infinite games whose winning sets are recognized by nondeterministic pushdown automata with various acceptance conditions, e.g. , safety, reachability and co-Buchi conditions. In terms of the foundational program “Reverse Mathematics”, the determinacy strength of such games is measured by the complexity of a winning strategy required by the determinacy. Infinite games recognized by nondeterministic pushdown automata have some resemblance to those by deterministic 2-stack visibly pushdown automata with the same acceptance conditions. So, we first investigate the determinacy of games recognized by deterministic 2-stack visibly pushdown automata, together with that by nondeterministic ones. Then, for instance, we prove that the determinacy of games recognized by pushdown automata with a reachability condition is equivalent to the weak Konig lemma, stating that every infinite binary tree has an infinite path. While the determinacy for pushdown ω -languages with a Buchi condition is known to be independent from ZFC, we here show that for the co-Buchi condition, the determinacy is exactly captured by ATR0 , another popular system of reverse mathematics asserting the existence of a transfinite hierarchy produced by iterating arithmetical comprehension along a given well-order. Finally, we conclude that all results for pushdown automata in this paper indeed hold for 1-counter automata.

The family of languages recognized by deterministic input-driven pushdown automata (IDPDA; a.k.a. visibly pushdown automata, a.k.a. nested word automata) is known to be closed under concatenation, Kleene star and reversal (under natural assumptions on the partition of the alphabet). As shown by Alur and Madhusudan (2004) 2, the Kleene star and the reversal of an n-state IDPDA can be represented by an IDPDA with 2 O ( n 2 ) states, while concatenation of an m-state and an n-state IDPDA is represented by an IDPDA with 2 O ( ( m + n ) 2 ) states. This paper presents more efficient constructions for the Kleene star and for the reversal, which yield 2 ( n log n ) states, as well as an m 2 ( n log n ) -state construction for the concatenation. These constructions are optimal up to a factor in the exponent, due to the close lower bounds previously established by Piao and Salomaa (2009) 27.

Pushdown automata may contain transitions that are never used in any accepting run of the automaton. We present an algorithm for detecting such useless transitions. A finite automaton that captures the possible stack content during runs of the pushdown automaton, is first constructed in a forward procedure to determine which transitions are reachable, and then employed in a backward procedure to determine which of these transitions can lead to a final state. An implementation of the algorithm is shown to exhibit a favorable performance.

Visibly Pushdown Automata ( VPA ) are a special case of pushdown machines where the stack operations are driven by the input. In this paper, we consider VPA with multiple stacks , namely n-VPA , with n > 1 . These automata introduce a useful model to effectively describe concurrent pushdown systems using a simple communication mechanism between stacks. We show that n -VPA are strictly more expressive than VPA. Indeed, n -VPA accept some context-sensitive languages that are not context-free and some context-free languages that are not accepted by any VPA. Nevertheless, we show that the class of languages accepted by n -VPA is closed under union and intersection. On the contrary, this class turns out to be neither closed under complementation nor determinizable. Moreover, we show that the emptiness problem for n -VPA is undecidable. By adding an ordering constraint on stacks ( n -OVPA), decidability of emptiness can be recovered, as well as the closure under complementation. Using these properties along with the automata-theoretic approach, one can prove that the model checking problem over n -OVPA models against n -OVPA specifications is decidable.

The paper introduces a subfamily of synchronized alternating pushdown automata, deterministic synchronized alternating pushdown automata, and a subfamily of conjunctive grammars, L R ( 0 ) conjunctive grammars. It is shown that deterministic synchronized alternating pushdown automata and L R ( 0 ) conjunctive grammars have the same recognition/generation power, analogously to the classical equivalence between acceptance by empty stack of deterministic pushdown automata and L R ( 0 ) grammars. These models form the theoretical basis for efficient linear time parsing of a subfamily of conjunctive languages which properly includes the classical L R ( 0 ) languages.

New algorithms for the determinization of nondeterministic visibly and nondeterministic real-time height-deterministic pushdown automata are presented. The algorithms improve the results of existing algorithms. They construct only accessible states and necessary pushdown symbols of the resulting deterministic pushdown automata. HighlightsTracking pushdown symbols which can appear on top of pushdown store for each state.Generating pop (return) transition only for possible top pushdown symbols for each state.Overall generating only accessible states and necessary pushdown store symbols.Visibly pushdown automata determinization algorithm.Height-deterministic (real-time) automata determinization algorithm.

We investigate subfamilies of context-free languages that share two important properties. The languages are accepted by input-driven pushdown automata as well as by a reversible pushdown automata. So, the languages are input driven and reversible at the same time. This intersection can be defined on the underlying language families or on the underlying machine classes. It turns out that the latter class is properly included in the former. The relationships between the language families obtained in this way and to reversible context-free languages as well as to input-driven languages are studied. In general, a hierarchical inclusion structure within the real-time deterministic context-free languages is obtained. Finally, the closure properties of these families under the standard operations are investigated and it turns out that all language families introduced are anti-AFLs.

Weighted restarting automata have been introduced to study quantitative aspects of computations of restarting automata. Here we study the special case that words over a given (output) alphabet are assigned as weights to the transitions of a restarting automaton. In this way the automaton is extended to define a mapping from the words over its input alphabet into the semiring of formal languages over a given (output) alphabet, generalizing the restarting transducers introduced by Hundeshagen (2013) 7. We establish that the monotone restarting transducers that are allowed to use auxiliary symbols characterize the class of almost-realtime pushdown relations, and we characterize the deterministic pushdown functions by a particular type of deterministic monotone restarting transducer. Further, we show that already linearly bounded (word-)weighted monotone restarting automata that use auxiliary symbols are more expressive than the corresponding restarting transducers, both in the deterministic as well as in the nondeterministic case. Finally, we prove that for (word-)weighted monotone restarting automata with auxiliary symbols, the variant that may keep on reading after performing a rewrite step (the so-called RRWW-automaton) is strictly more expressive than the variant that must restart immediately after performing a rewrite step (the so-called RWW-automaton), which again holds in the deterministic as well as in the nondeterministic case. This is the first time that a version of the monotone RRWW-automaton is shown to differ in expressive power from the corresponding version of the monotone RWW-automaton.

Motivated by the concept of fuzzy finite automata and fuzzy pushdown automata, we investigate a novel fuzzy state grammars and fuzzy deep pushdown automata concept. This concept represents a natural extension of contemporary state grammar and deep pushdown automaton, making them more robust in terms of imprecision, errors, and uncertainty. It has been proved that we can construct fuzzy deep pushdown automata from fuzzy state grammars and vice-versa. Furthermore, it has been proved that if fuzzy deep pushdown automaton Mfd is constructed from fuzzy state grammar Gfs then L(Mfd) = L(Gfs). In other words, for any string α ∈ � ∗ , μ(α; α ∈ L(Gfs)) = μ(α; α ∈ L(Mfd)) where μ denotes the membership of a string.

Flip-pushdown automata are pushdown automata with an extra ability to reverse the contents of the pushdown store. A generalisation of the pumping lemma for context-free languages is presented, which applies to the families of languages accepted by flip-pushdown automata with k pushdown flips, for an arbitrary constant k. The presented result gives rise to a new technique for disproving existence of flip-pushdown automata with a constant number of flips, which is significantly simpler compared to methods used for this purpose so far.

Restrictions of reversal-bounded multicounter machines are studied; in particular, those that cannot subtract from any counter until it has reached the end of the input. It is proven that this does not alter the languages accepted when the machines are nondeterministic. When the machines are deterministic, the languages (denoted by eDCM ) are shown to coincide with those accepted by deterministic Parikh automata, but are strictly contained in the class of languages accepted by machines without this condition. It then follows that all commutative semilinear languages are in this restricted class. A number of decidability and complexity properties are shown, such as the ability to test, given a deterministic pushdown automaton (even if augmented by a fixed number of reversal-bounded counters), whether it is commutative. Lastly, this deterministic family, eDCM , is shown to be the smallest family of languages closed under commutative closure, right quotient with regular languages and inverse deterministic finite transductions.

We present several new results on minimal space requirements to recognize a nonregular language: (i) realtime nondeterministic Turing machines can recognize a nonregular unary language within weak log log n space, (ii) log log n is a tight space lower bound for accepting general nonregular languages on weak realtime pushdown automata, (iii) there exist unary nonregular languages accepted by realtime alternating one-counter automata within weak log n space, (iv) there exist nonregular languages accepted by two-way deterministic pushdown automata within strong log log n space, and, (v) there exist unary nonregular languages accepted by two-way one-counter automata using quantum and classical states with middle log n space and bounded error.

This chapter covers pushdown automata and parsing algorithms with emphasis on the application to syntax analysis. We start by introducing general and deterministic pushdown automata as recognizers of context-free and deterministic context-free languages defined by grammars. Then we present the classical deterministic bottom-up (LR(1)) and top-down (LL(1)) parsing methods, by adopting a novel approach that allows for the analysis of the languages defined by Extended BNF (EBNF) grammars, i.e., grammars that admit a regular expression in the right part of the rules. The EBNF grammars are here represented by a network of recursive finite automata. The extended LL(1) (ELL(1)) parsers are presented as a special case of the ELR(1) algorithms, such that simpler and more compact parser implementations by means of recursive procedures are possible. The classical Earley method for parsing general context-free grammars is also presented in a form generalized to EBNF. The chapter continues with an innovative parallel parsing technique based on operator-precedence grammars, suitable for parsing large files. At the end, we outline simple methods for parser error recovery and we mention incremental parsing.

Many applications process some form of tree-structured or recursively-nested data, such as parsing XML or JSON web content as well as various data mining tasks. Typical CPU processing solutions are hindered by branch misprediction penalties while attempting to reconstruct nested structures and also by irregular memory access patterns. Recent work has demonstrated improved performance for many data processing applications through memory-centric automata processing engines. Unfortunately, these architectures do not support a computational model rich enough for tasks such as XML parsing. In this paper, we present ASPEN, a general-purpose, scalable, and reconfigurable memory-centric architecture for processing of tree-like data. We take inspiration from previous automata processing architectures, but support the richer deterministic pushdown automata computational model. We propose a custom datapath capable of performing the state matching, stack manipulation, and transition routing operations of pushdown automata, all efficiently stored and computed in memory arrays. Further, we present compilation algorithms for transforming large classes of existing grammars to pushdown automata executable on ASPEN, and demonstrate their effectiveness on four different languages: Cool (object oriented programming), DOT (graph visualization), JSON, and XML. Finally, we present an empirical evaluation of two application scenarios for ASPEN: XML parsing, and frequent subtree mining. The proposed architecture achieves an average 704.5 ns per KB parsing XML compared to 9983 ns per KB in a state-of-the-art XML parser across 23 benchmarks. We also demonstrate a 37.2x and 6x better end-to-end speedup over CPU and GPU implementations of subtree mining.

This paper describes two steps in the generalization of supervisory control theory to situations where the specification is modeled by a deterministic context free language (DCFL). First, it summarizes a conceptual iterative algorithm from Schneider et al. (2014) solving the supervisory control problem for language models. This algorithm involves two basic iterative functions. Second, the main part of this paper presents an implementable algorithm realizing one of these functions, namely the calculation of the largest controllable marked sublanguage of a given DCFL. This algorithm least restrictively removes controllability problems in a deterministic pushdown automaton realizing this DCFL.

The article surveys some decidability results concerning simplification problems for DPDAs on infinite words (ω-DPDAs). We summarize some recent results on the regularity problem, which asks for a given ω-DPDA, whether its language can also be accepted by a finite automaton. The results also give some insights on the equivalence problem for a subclass of ω-DPDA. Furthermore, we present some new results on the parity index problem for ω-DPDAs. For the specification of a parity condition, the states of the ω-DPDA are assigned priorities (natural numbers), and a run is accepting if the highest priority that appears infinitely often during a run is even. The basic simplification question asks whether one can determine the minimal number of priorities that are needed to accept the language of a given ω-DPDA. We provide some decidability results on variations of this question for some classes of ω-DPDAs.

In the presented paper we discuss pure versions of pushdown automata that have no extra non-input symbols. More specifically, we study pure multi-pushdown automata, which have several pushdown lists. We restrict these automata by the total orders defined over their pushdowns or alphabets and determine the accepting power of the automata restricted in this way. Moreover, we explain the significance of the achieved results and relate them to some other results in the automata theory.

We present two restricted versions of one-tape Turing machines. Both characterize the class of context-free languages. In the first version, proposed by Hibbard in 1967 and called limited automata , each tape cell can be rewritten only in the first d visits, for a fixed constant d ≥ 2. Furthermore, for d = 2 deterministic limited automata are equivalent to deterministic pushdown automata, namely they characterize deterministic context-free languages. Further restricting the possible operations, we consider strongly limited automata . These models still characterize context-free languages. However, the deterministic version is less powerful than the deterministic version of limited automata. In fact, there exist deterministic context-free languages that are not accepted by any deterministic strongly limited automaton.

Checking whether one formal language is included in another is important in many verification tasks. In this article, we provide solutions for checking the inclusion of languages given by visibly pushdown automata over both finite and infinite words. Visibly pushdown automata are a richer automaton model than the classical finite-state automata, which allows one, for example, to reason about the nesting of procedure calls in the executions of recursive imperative programs. The presented solutions do not rely on explicit automaton constructions for determinization and complementation. Instead, they are more direct and generalize the so-called Ramsey-based inclusion-checking algorithms, which apply to classical finite-state automata and proved to be effective there to visibly pushdown automata. We also experimentally evaluate these algorithms, demonstrating the virtues of avoiding explicit determinization and complementation constructions.

We introduce asynchronous variants of the parallel communicating systems of pushdown automata of Csuhaj-Varjú et al. These are obtained by using a response symbol in addition to the usual query symbols. Our main result states that centralized asynchronous parallel communicating systems of pushdown automata of degree n that work in returning mode have exactly the same expressive power as n-head pushdown automata. This holds in the nondeterministic as well as in the deterministic case. In addition, it is shown that the class of binary relations that is computed by centralized asynchronous parallel communicating systems of pushdown automata of degree two that are working in returning mode coincides with the class of pushdown relations.

Finite state automata recognize regular languages which can be used in text processing, compilers, and hardware design. Two head finite automata accept linear context free languages. In addition, pushdown automata are able to recognize context free languages which can be used in programming languages and artificial intelligence. The finite automaton has deterministic and non-deterministic version likewise the two head finite automata and the pushdown automata. The deterministic version of these machines is such that there is no choice of move in any situation while the non-deterministic version has a choice of move. In this research the 2-head pushdown automata are described which is more powerful than the pushdown automata and it is able to recognize some non-context free languages as well. During this work, the main task is to characterize these machines.

We study the problem of trimming visibly pushdown automata (VPA). We first describe a polynomial time procedure which, given a visibly pushdown automaton that accepts only well-nested words, returns an equivalent visibly pushdown automaton that is trimmed. We then show how this procedure can be lifted to the setting of arbitrary VPA. Furthermore, we present a way of building, given a VPA, an equivalent VPA which is both deterministic and trimmed. Last, our trimming procedures can be applied to weighted VPA.

Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥ 2, these devices characterize the class of context-free languages. We investigate the equivalence between 2-limited automata and pushdown automata, comparing the relative sizes of their descriptions. We prove exponential upper and lower bounds for the sizes of pushdown automata simulating 2-limited automata. In the case of the conversion of deterministic 2-limited automata into deterministic pushdown automata the upper bound is double exponential and we conjecture that it cannot be reduced. On the other hand, from pushdown automata we can obtain equivalent 2-limited automata of polynomial size, also preserving determinism. From our results, it follows that the class of languages accepted by deterministic 2-limited automata coincides with the class of deterministic context-free languages.

Part 2: Contributed Papers; International audience; The quotient of a formal language K by another language L is the set of all strings obtained by taking a string from K that ends with a suffix from L, and removing that suffix. The quotient of a regular language by any language is always regular, whereas the context-free languages and many of their subfamilies, such as the linear and the deterministic languages, are not closed under the quotient operation. This paper establishes the closure of the family of input-driven pushdown automata (IDPDA), also known as visibly pushdown automata, under the quotient operation. A construction of automata representing the result of the operation is given, and its state complexity with respect to nondeterministic IDPDA is shown to be $m^2n + O(m)$, where m and n is the number of states in the automata recognizing K and L, respectively.

We study the descriptional cost of removing nondeterminism in constant height pushdown automata-i.e., pushdown automata with a built-in constant limit on the height of the pushdown. We show a double-exponential size increase when converting a constant height nondeterministic pushdown automaton into an equivalent deterministic device. Moreover, we prove that such a double-exponential blow-up cannot be avoided by certifying its optimality. As a direct consequence, we get that eliminating nondeterminism in classical finite state automata is single-exponential even with the help of a constant height pushdown store.

In this paper we introduce a subfamily of synchronized alternating pushdown automata, one-turn synchronized alternating pushdown automata, which accept the same class of languages as those generated by linear conjunctive grammars. This equivalence of models of computation is analogous to the classical equivalence between one-turn pushdown automata and linear grammars, thus strengthening the claim of synchronized alternating pushdown automata as a natural counterpart of conjunctive grammars.

A one-counter automaton is a pushdown automaton with a singleton stack alphabet, where stack emptiness can be tested; it is a real-time automaton if it contains no e-transitions. We study the computational complexity of the problems of equivalence and regularity (i.e. semantic finiteness) on real-time one-counter automata. The first main result shows PSPACE -completeness of bisimulation equivalence; this closes the complexity gap between decidability 23] and PSPACE -hardness 25]. The second main result shows NL -completeness of language equivalence of deterministic real-time one-counter automata; this improves the known PSPACE upper bound (indirectly shown by Valiant and Paterson 27]). Finally we prove P -completeness of the problem if a given one-counter automaton is bisimulation equivalent to a finite system, and NL -completeness of the problem if the language accepted by a given deterministic real-time one-counter automaton is regular. Bisimulation equivalence is PSPACE -complete for real-time one-counter automata.Language equivalence is NL -complete for deterministic real-time one-counter automata.Finiteness w.r.t. bisimilarity is P -complete for real-time one-counter automata.Regularity is NL -complete for deterministic real-time one-counter automata.

We describe the mechanisation of some foundational results in the theory of context-free languages (CFLs), using the HOL4 system. We focus on pushdown automata (PDAs). We show that two standard acceptance criteria for PDAs (''accept-by-empty-stack'' and ''accept-by-final-state'') are equivalent in power. We are then able to show that the pushdown automata (PDAs) and context-free grammars (CFGs) accept the same languages by showing that each can emulate the other. With both of these models to hand, we can then show a number of basic, but important results. For example, we prove the basic closure properties of the context-free languages such as union and concatenation. Along the way, we also discuss the varying extent to which textbook proofs (we follow Hopcroft and Ullman) and our mechanisations diverge: sometimes elegant textbook proofs remain elegant in HOL; sometimes the required mechanisation effort blows up unconscionably.

In this paper we study the model-checking problem for probabilistic pushdown automata (pPDA) and branching-time probabilistic logics PCTL and PCTL^@?. We show that model-checking pPDA against general PCTL formulae is undecidable, but we yield positive decidability results for the qualitative fragments of PCTL and PCTL^@?. For these fragments, we also give a complete complexity classification.

In this paper a step towards the generalization of supervisory control theory to situations where the specification is modeled by a deterministic pushdown automaton (DPDA) is provided. In particular, this paper presents an algorithm to calculate the largest controllable marked sublanguage of a given deterministic context free language (DCFL) by least restrictively removing controllability problems in a DPDA realization of this DCFL. It also provides a counterexample which shows that the algorithm by Griffin (2008) intended to solve the considered problem is not minimally restrictive.

Information-Based Access Control (IBAC) has been proposed as an improvement to History-Based Access Control (HBAC) model. In modern component-based systems, these access control models verify that all the code responsible for a security-sensitive operation is sufficiently authorized to execute that operation. The HBAC model, although safe, may incorrectly prevent the execution of operations that should be executed. The IBAC has been shown to be more precise than HBAC maintaining its safety level while allowing sufficiently authorized operations to be executed. However the verification problem of IBAC program has not been discussed. This paper presents a formal model for IBAC programs based on extended weighted pushdown systems (EWPDS). The mapping process between the IBAC original semantics and the EWPDS structure is described. Moreover, the verification problem for IBAC programs is discussed and several typical IBAC program examples using our model are implemented.

We show that every language accepted by a nondeterministic auxiliary pushdown automaton in polynomial time (that is, every language in SAC^1 = Log(CFL)) can be accepted by a symmetric auxiliary pushdown automaton in polynomial time.