No label defined (Q3698787)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3922633
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3922633

      Statements

      1985
      0 references
      omega regularity
      0 references
      infinite words
      0 references
      complementing Büchi automata
      0 references
      decision procedure
      0 references
      Extended Temporal Logic
      0 references
      satisfiability problem
      0 references
      repeating acceptance
      0 references
      [For the entire collection see Zbl 0563.00018.] Let \(A=(\Sigma,S,\rho,s_ o,F)\) be a nondeterministic Büchi automaton, where \(\Sigma\) is a finite alphabet, S the finite set of states, \(\rho\) the transition relation, F the acceptable states. An infinite word \(w\in \Sigma^{\omega}\) is acceptable by A iff there is a run \(s_ 0,s_ 1,...\), where \(s_ i\in \rho (s_{i-1},w_ i)\) such that for some \(s\in F\) there are infinitely many i's such that \(s_ i=s\). This classical notion has many applications, especially in proving decidability of different theories. Decidability proofs base on the fact that the complement \(\overline{L(A)}\) of the language L(A) acceptable by A is also acceptable by a Büchi automaton. The standard constructions required double exponential blow-up, i.e. if A has n states, then \(\bar A\) has \(c^{c^ n}\) states, for some \(c>1\). The paper provides a construction reducing the number of states of \(\bar A\) to \(O(16^{n^ 2})\). The immediate applications to Extended Temporal Logic, where infinite behaviour of programs is considered, are presented. In particular, the satisfiability problem of Extended Temporal Logic with repeating acceptance is proved to be P-space complete.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references