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
0.86519855260849
0 references
0.8561961650848389
0 references
0.8472362756729126
0 references
0.8469294905662537
0 references
0.8445656895637512
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