loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
21st Annual IEEE Symposium on Logic in Computer Science (LICS'06)
Monadic Chain Logic Over Iterations and Applications to Pushdown Systems
Seattle, Washington
August 12-August 15
ISBN: 0-7695-2631-4
ASCII Text
x 
 
Dietrich Kuske, Markus Lohrey, "Monadic Chain Logic Over Iterations and Applications to Pushdown Systems," Logic in Computer Science, Symposium on, pp. 91-100, 21st Annual IEEE Symposium on Logic in Computer Science (LICS'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/LICS.2006.35,
author = {Dietrich Kuske and Markus Lohrey},
title = {Monadic Chain Logic Over Iterations and Applications to Pushdown Systems},
journal ={Logic in Computer Science, Symposium on},
volume = {0},
year = {2006},
issn = {1043-6871},
pages = {91-100},
doi = {http://doi.ieeecomputersociety.org/10.1109/LICS.2006.35},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Logic in Computer Science, Symposium on
TI - Monadic Chain Logic Over Iterations and Applications to Pushdown Systems
SN - 1043-6871
SP91
EP100
A1 - Dietrich Kuske,
A1 - Markus Lohrey,
PY - 2006
KW - null
VL - 0
JA - Logic in Computer Science, Symposium on
ER -
 
Dietrich Kuske, Universitat Leipzig, Germany
Markus Lohrey, Universitat Stuttgart, Germany
Logical properties of iterations of relational structures are studied and these decidability results are applied to the model checking of a powerful extension of pushdown systems. It is shown that the monadic chain theory of the iteration of a structure A (in the sense of Shelah and Stupp) is decidable in case the first-order theory of the structure A is decidable. This result fails if Muchnik?s clone-predicate is added. A model of pushdown automata, where the stack alphabet is given by an arbitrary (possibly infinite) relational structure, is introduced. If the stack structure has a decidable first-order theory with regular reachability predicates, then the same holds for the configuration graph of this pushdown automaton. This result follows from our decidability result for the monadic chain theory of the iteration.
Citation:
Dietrich Kuske, Markus Lohrey, "Monadic Chain Logic Over Iterations and Applications to Pushdown Systems," lics, pp.91-100, 21st Annual IEEE Symposium on Logic in Computer Science (LICS'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.