This HTML5 document contains 37 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
n13http://www.lsv.ens-cachan.fr/~gastin/ltl2ba/
foafhttp://xmlns.com/foaf/0.1/
n19https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
n18http://sourceforge.net/projects/ltl3ba/
n4http://
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
goldhttp://purl.org/linguistics/gold/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Linear_temporal_logic_to_Büchi_automaton
rdfs:label
Linear temporal logic to Büchi automaton
rdfs:comment
In formal verification,finite state model checking needs to find a Büchi automaton (BA) equivalent to a given linear temporal logic (LTL) formula, i.e., such that the LTL formula and the BA recognize the same ω-language. There are algorithms that translate an LTL formula to a BA. This transformation is normally done in two steps. The first step produces a generalized Büchi automaton (GBA) from a LTL formula. The second step translates this GBA into a BA, which involves a relatively easy construction. Since LTL is strictly less expressive than BA, the reverse construction is not always possible.
dcterms:subject
dbc:Model_checking dbc:Temporal_logic dbc:Automata_(computation)
dbo:wikiPageID
31670156
dbo:wikiPageRevisionID
1101824819
dbo:wikiPageWikiLink
dbr:Linear_temporal_logic dbc:Model_checking dbr:Pierre_Wolper dbc:Temporal_logic dbc:Automata_(computation) dbr:Generalized_Büchi_automaton dbr:Formal_verification dbr:Moshe_Y._Vardi dbr:Model_checking dbr:Ω-language dbr:Büchi_automaton dbr:Labeled_generalized_Büchi_automaton
dbo:wikiPageExternalLink
n4:spot.lip6.fr n13: n18:
owl:sameAs
freebase:m.0gmdkmq wikidata:Q6553530 n19:4qH7W
dbp:wikiPageUsesTemplate
dbt:Reflist dbt:Pre dbt:Hidden_end dbt:Hidden_begin
dbp:bg
lightgrey
dbp:title
Proof of correctness of the above construction
dbp:titlestyle
background:lightblue;
dbo:abstract
In formal verification,finite state model checking needs to find a Büchi automaton (BA) equivalent to a given linear temporal logic (LTL) formula, i.e., such that the LTL formula and the BA recognize the same ω-language. There are algorithms that translate an LTL formula to a BA. This transformation is normally done in two steps. The first step produces a generalized Büchi automaton (GBA) from a LTL formula. The second step translates this GBA into a BA, which involves a relatively easy construction. Since LTL is strictly less expressive than BA, the reverse construction is not always possible. The algorithms for transforming LTL to GBA differ in their construction strategies but they all have a common underlying principle, i.e., each state in the constructed automaton represents a set of LTL formulas that are expected to be satisfied by the remaining input word after occurrence of the state during a run.
gold:hypernym
dbr:Algorithms
prov:wasDerivedFrom
wikipedia-en:Linear_temporal_logic_to_Büchi_automaton?oldid=1101824819&ns=0
dbo:wikiPageLength
20712
foaf:isPrimaryTopicOf
wikipedia-en:Linear_temporal_logic_to_Büchi_automaton