Weak Büchi automaton

In computer science and automata theory, a Weak Büchi automaton is a formalism which represents a set of infinite words. A Weak Büchi automaton is a modification of Büchi automaton such that for all pair of states $q$ and $q'$ belonging to the same strongly connected component, $q$ is accepting if and only if $q'$ is accepting.

A Büchi automaton accepts a word $w$ if there exists a run, such that at least one state occurring infinitely often in the final state set $F$ . For Weak Büchi automata, this condition is equivalent to the existence of a run which ultimately stays in the set of accepting states.

Weak Büchi automata are strictly less-expressive than Büchi automaton and than Co-Büchi automaton.

Properties

The deterministic Weak Büchi automata can be minimized in time $O(n\log(n))$ .[1]

The languages accepted by Weak Büchi automata are closed under union, intersection and complementation.

Non-deterministic Weak Büchi automata are more expressive than Weak Büchi automata. As an example, the language $(a+b)^{*}b^{\omega }$ can be decided by a weak Büchi automaton but by no deterministic Büchi automaton

gollark: <@184468521042968577> You know, a structure of ```lua{ ["a/b/c"] = "hugeblank's bad code"}```would be better for writes and stuff but worse for listing.Also, you can convert paths to a "canonical form" with `fs.combine(path, "") `.

gollark: https://pastebin.com/G2PMCNhFSkynet: simple websocket-based data transfer (ask if you want the server code).Use with `local skynet = require "skynet"````skynet.receive(channel) - receive a message on the given channelskynet.send(channel, data) - send a message (can be any JSON-serializable type) on the given channelskynet.listen() - convert "websocket_message"s to "skynet_message"sskynet.open(channel) - kind of internal, open "channel" - returns a raw websocket, which you must not use or else.```

gollark: I made a coroutine manager which kills the regular CC loop (run rednet & shell in `parallel.waitForAny`) and provides a convenient API for running your own processes.https://pastebin.com/HL0SZhJG

gollark: Live Game of Life flooring displayed as actual blocks on the floor.https://pastebin.com/kNG4K1Kv

gollark: A somewhat bad demo of ARC (https://forums.computercraft.cc/index.php?topic=10): basically, it displays text on overlay glasses when you're near "beacons" which broadcast text to display. Look at the top right, the top left/bottom left are not ARC stuff.

References

Löding, Christof (2001). "Efficient Minimization of Deterministic Weak ω-Automata". Information Processing Letters. 79 (3): 105–109. doi:10.1016/S0020-0190(00)00183-6.

Boigelot, Bernard (3 July 2005). "An effective decision procedure for linear arithmetic over the integers and reals" (PDF). ACM Transactions on Computational Logic. 6 (3): 614–633. doi:10.1145/1071596.1071601.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Löding, Christof (2001). "Efficient Minimization of Deterministic Weak ω-Automata". Information Processing Letters. 79 (3): 105–109. doi:10.1016/S0020-0190(00)00183-6.