S | |
---|---|

[Saf89] | Shmuel Safra. Complexity of Automata on Infinite Objects. PhD thesis, Weizmann Institute of Science, Rehovot, Israel, March 1989. |

[Saf92] | Shmuel Safra. Exponential Determinization for ω-Automata with Strong-Fairness Acceptance Condition. In STOC'92, pages 272-282. ACM Press, 1992. |

[San05] | Sven Sandberg. Homing and Synchronizing Sequences. In MBTRS'04, Lecture Notes in Computer Science 3472, pages 5-33. Springer-Verlag, 2005. |

[San10] | Ocan Sankur. Model-checking robuste des automates temporisés via les machines à canaux. Mémoire de master, Lab. Spécification & Vérification, ENS Cachan, France, 2010. |

[San13] | Ocan Sankur. Robustness in Timed Automata: Analysis, Synthesis, Implementation. Thèse de doctorat, Lab. Spécification & Vérification, ENS Cachan, France, May 2013. |

[San15] | Ocan Sankur. Symbolic Quantitative Robustness Analysis of Timed Automata. In TACAS'15, Lecture Notes in Computer Science 9035, pages 484-498. Springer-Verlag, April 2015. |

[Sar93] | Ramnath Sarnath. Doubly Logarithmic Time Parallel Sorting. Technical Report 93-01, suny, January 1993. |

[Saw03] | Zdeněk Sawa. Equivalence Checking of Non-flat Systems is EXPTIME-hard. In CONCUR'03, Lecture Notes in Computer Science 2761, pages 237-250. Springer-Verlag, August 2003. |

[SB00] | Fabio Somenzi and Roderick Bloem. Efficient Büchi Automata from LTL Formulae. In CAV'00, Lecture Notes in Computer Science 1855, pages 248-263. Springer-Verlag, July 2000. |

[SB11] | Fabio Somenzi and Steven Bradley. IC3: where monolithic and incremental meet. In FMCAD'11, pages 3-8. October 2011. |

[SBM11] | Ocan Sankur, Patricia Bouyer, and Nicolas Markey. Shrinking Timed Automata. In FSTTCS'11, Leibniz International Proceedings in Informatics 13, pages 90-102. Leibniz-Zentrum für Informatik, December 2011. |

[SBM14] | Ocan Sankur, Patricia Bouyer, and Nicolas Markey. Shrinking Timed Automata. Information and Computation 234:107-132. Elsevier, February 2014. |

[SBM+13] | Ocan Sankur, Patricia Bouyer, Nicolas Markey, and Pierre-Alain Reynier. Robust Controller Synthesis in Timed Automata. In CONCUR'13, Lecture Notes in Computer Science 8052, pages 546-560. Springer-Verlag, August 2013. |

[SC85] | A. Prasad Sistla and Edmund M. Clarke. The Complexity of Propositional Linear Temporal Logics. Journal of the ACM 32(3):733-749. ACM Press, July 1985. |

[SC02] | Michael Soltys and Stephen A. Cook. The Proof Complexity of Linear Algebra. In LICS'02, pages 335-344. IEEE Comp. Soc. Press, July 2002. |

[Sch61] | Marcel-Paul Schützenberger. On the Definition of a Family of Automata. Information and Control 4(2-3):245-270. Academic Press, September 1961. |

[Sch98] | Stefan Schwendimann. A New One-Pass Tableau Calculus for PLTL. In TABLEAUX'98, Lecture Notes in Computer Science 1397, pages 277-292. Springer-Verlag, May 1998. |

[Sch01] | Philippe Schnoebelen. Spécification et Vérification des Systèmes Concurrents. Mémoire d'habilitation, Lab. Spécification & Vérification, ENS Cachan, France, October 2001. |

[Sch02] | Philippe Schnoebelen. Verifying Lossy Channel Systems has Nonprimitive Recursive Complexity. Information Processing Letters 83(5):251-261. Elsevier, September 2002. |

[Sch03] | Philippe Schnoebelen. The Complexity of Temporal Logic Model Checking. In AIML'02, pages 481-517. King's College Publications, 2003. |

[Sch03] | Philippe Schnoebelen. Oracle Circuits for Branching-Time Model Checking. In ICALP'03, Lecture Notes in Computer Science 2719, pages 790-801. Springer-Verlag, June 2003. |

[Sch04] | Pierre-Yves Schobbens. Alternating-Time Logic with Imperfect Recall. In LCMAS'03, Electronic Notes in Theoretical Computer Science 85(2), pages 82-93. Elsevier, April 2004. |

[Sch08] | Sven Schewe. ATL* Satisfiability Is 2EXPTIME-Complete. In ICALP'08, Lecture Notes in Computer Science 5126, pages 373-385. Springer-Verlag, July 2008. |

[Sch08] | Sven Schewe. Synthesis of Distributed Systems. PhD thesis, Saarland University, Germany, July 2008. |

[Sch13] | Sylvain Schmitz. Complexity Hierarchies Beyond Elementary. Research Report cs.CC/1312.5686, arXiv, December 2013. |

[Sch16] | Sylvain Schmitz. Complexity Hierarchies Beyond Elementary. ACM Transactions on Computation Theory 8(1):3:1-3:36. ACM Press, February 2016. |

[SE89] | Robert S. Streett and E. Allen Emerson. An Automata Theoretic Decision Procedure for the Propositional Mu-Calculus. Information and Computation 81(3):249-264. Academic Press, 1989. |

[See76] | Detlef G. Seese. Entscheidbarkeits- und Interpretierbarkeitsfragen monadischer Theorien zweiter Stufe gewisser Klassen von Graphen. PhD thesis, Humboldt-Universität zu Berlin, German Democratic Republic, 1976. |

[Ser04] | Olivier Serre. Vectorial Languages and Linear Temporal Logic. Theoretical Computer Science 310(1-3):79-116. Elsevier, January 2004. |

[Ser06] | Olivier Serre. Parity games played on transition graphs of one-counter processes. In FoSSaCS'06, Lecture Notes in Computer Science 3921, pages 337-351. Springer-Verlag, March 2006. |

[SF06] | Sven Schewe and Bernd Finkbeiner. Satisfiability and Finite Model Property for the Alternating-Time μ-Calculus. In CSL'06, Lecture Notes in Computer Science 4207, pages 591-605. Springer-Verlag, September 2006. |

[SF07] | Sven Schewe and Bernd Finkbeiner. Synthesis of Asynchronous Systems. In LOPSTR'06, Lecture Notes in Computer Science 4407, pages 127-142. Springer-Verlag, 2007. |

[SF07] | Mani Swaminathan and Martin Fränzle. A Symbolic Decision Procedure for Robust Safety of Timed Systems. In TIME'07, pages 192. IEEE Comp. Soc. Press, June 2007. |

[SFK08] | Mani Swaminathan, Martin Fränzle, and Joost-Pieter Katoen. The Surprising Robustness of (Closed) Timed Automata against Clock-Drift. In IFIPTCS'08, IFIP Conference Proceedings 273, pages 537-553. Springer-Verlag, September 2008. |

[She59] | John C. Shepherdson. The Reduction of Two-Way Automata to One-Way Automata. IBM Journal of Research and Development 3:198-200. April 1959. |

[Sho08] | Yoav Shoham. Computer Science and Game Theory. Communications of the ACM 51(8):74-79. ACM Press, August 2008. |

[Sip80] | Michael Sipser. Halting Space-bounded Computations. Theoretical Computer Science 10(3):335-338. Elsevier, 1980. |

[Sip97] | Michael Sipser. Introduction to the theory of computation. PWS Publishing Company, 1997. |

[Sip06] | Michael Sipser. Introduction to the theory of computation. Thomson Course Technology, 2006. |

[Sis83] | A. Prasad Sistla. Theoretical Issues in the Design and Verification of Distributed Systems. PhD thesis, Harvard University, 1983. |

[SJ01] | Zdeněk Sawa and Petr Jančar. P-hardness of Equivalence Testing on Finite State Processes. In SOFSEM'01, Lecture Notes in Computer Science 2234, pages 326-335. Springer-Verlag, November 2001. |

[SKL06] | Oleg Sokolsky, Sampath Kannan, and Insup Lee. Simulation-Based Graph Similarity. In TACAS'06, Lecture Notes in Computer Science 3920, pages 426-440. Springer-Verlag, March 2006. |

[SKS03] | Shoham Shamir, Orna Kupferman, and Eli Shamir. Branching-Depth Hierarchies. In EXPRESS'00, Electronic Notes in Theoretical Computer Science 39(1). Elsevier, February 2003. |

[Sla05] | John K. Slaney. Semipositive LTL with an Uninterpreted Past Operator. Logic Journal of the IGPL 13(2):211-229. Oxford University Press, March 2005. |

[SLB09] | Yoav Shoham and Kevin Leyton-Brown. Multiagent Systems – Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2009. |

[SLS+14] | Youcheng Sun, Giuseppe Lipari, Romain Soulat, Laurent Fribourg, and Nicolas Markey. Component-Based Analysis of Hierarchical Scheduling using Linear Hybrid Automata. In RTCSA'14. IEEE Comp. Soc. Press, August 2014. |

[SLT98] | Meera Sampath, Stéphane Lafortune, and Demosthenis Teneketzis. Active diagnosis of discrete-event systems. IEEE Transactions on Automatic Control 43(7):908-929. IEEE Comp. Soc. Press, July 1998. |

[SM73] | Larry J. Stockmeyer and Albert R. Meyer. Word Problems Requiring Exponential Time: Preliminary Report. In STOC'73, pages 1-9. ACM Press, April 1973. |

[Sor02] | Maria Sorea. A Decidable Fixpoint Logic for Time-Outs. In CONCUR'02, Lecture Notes in Computer Science 2421, pages 255-271. Springer-Verlag, August 2002. |

[SPN+08] | P. Vijay Suman, Paritosh K. Pandya, Shankara Narayanan Krishna, and Lakshmi Manasa. Timed Automata with Integer Resets: Language Inclusion and Expressiveness. In FORMATS'08, Lecture Notes in Computer Science 5215, pages 78-92. Springer-Verlag, September 2008. |

[SR99] | Pierre-Yves Schobbens and Jean-François Raskin. The Logic of "Initially" and "Next". Information Processing Letters 69(5):221-225. Elsevier, 1999. |

[Srb02] | Jiří Srba. Undecidability of Weak Bisimulation for Pushdown Processes. In CONCUR'02, Lecture Notes in Computer Science 2421, pages 579-593. Springer-Verlag, August 2002. |

[SRH02] | Pierre-Yves Schobbens, Jean-François Raskin, and Thomas A. Henzinger. Axioms for Real-Time Logics. Theoretical Computer Science 274(1-2):151-182. Elsevier, March 2002. |

[SRS09] | Anu Singh, C. R. Ramakrishnan, and Scott A. Smolka. Query-Based Model Checking of Ad Hoc Network Protocols. In CONCUR'09, Lecture Notes in Computer Science 5710, pages 603-619. Springer-Verlag, September 2009. |

[SS78] | William J. Sakoda and Michael Sipser. Nondeterminism and the Size of Two Way Finite Automata. In STOC'78, pages 275-286. ACM Press, May 1978. |

[SS82] | James A. Storer and Thomas G. Szymanski. Data Compression via Textual Substitution. Journal of the ACM 29(4):928-951. ACM Press, October 1982. |

[SS02] | Vladimiro Sassone and Paweł Sobocoński. Deriving Bisimulationn Congruences: A 2-Categorical Approach. In EXPRESS'02, Electronic Notes in Theoretical Computer Science 68(2), pages 107-126. Elsevier, August 2002. |

[SSL+95] | Meera Sampath, Raja Sengupta, Stéphane Lafortune, Kasim Sinnamohideen, and Demosthenis Teneketzis. Diagnosability of discrete-event systems. IEEE Transactions on Automatic Control 40(9):1555-1575. IEEE Comp. Soc. Press, September 1995. |

[SSL+96] | Meera Sampath, Raja Sengupta, Stéphane Lafortune, Kasim Sinnamohideen, and Demosthenis Teneketzis. Failure diagnosis using discrete-event models. IEEE Transactions on Computers 35(1):105-124. IEEE Comp. Soc. Press, January 1996. |

[SSS+01] | Hiroshi Sakamoto, Shinichi Shimozono, Ayumi Shinohara, and Masayuki Takeda. On the Minimization Problem of Text Compression Scheme by a Reduced Grammar Transform. Technical Report 195, Department of Informatics, Kyushu University, Japan, August 2001. |

[ST03] | Roberto Sebastiani and Stefano Tonetta. "More Deterministic" vs. "Smaller" Büchi Automata for Efficient LTL Model Checking. In CHARME'03, Lecture Notes in Computer Science 2860. Springer-Verlag, October 2003. |

[ST17] | Ocan Sankur and Jean-Pierre Talpin. An Abstraction Technique For Parameterized Model Checking of Leader Election Protocols: Application to FTSP. In TACAS'17, Lecture Notes in Computer Science 10205. Springer-Verlag, April 2017. |

[Sta17] | Daniel Stan. Randomized strategies in concurrent games. Thèse de doctorat, Lab. Spécification & Vérification, ENS Cachan, France, March 2017. |

[Sti95] | Colin Stirling. Local Model Checking Games (Extended Abstract). In CONCUR'95, Lecture Notes in Computer Science 962, pages 1-11. Springer-Verlag, August 1995. |

[Sto74] | Larry J. Stockmeyer. The Complexity of Decision Problems in Automata Theory and Logic. PhD thesis, MIT, 1974. |

[Sto76] | Larry J. Stockmeyer. The Polynomial-Time Hierarchy. Theoretical Computer Science 3(1):1-22. Elsevier, 1976. |

[Sto87] | Larry J. Stockmeyer. Classifying the Computational Complexity of Problems. Journal of Symbolic Logic 52(1):1-43. Association for Symbolic Logic, March 1987. |

[Str52] | Arthur N. Strahler. Hypsometric (area-altitude) analysis of erosional topography. Geological Society of America Bulletin 63(11):1117-1142. Geological Society of America, November 1952. |

[Str04] | Jan Strejček. Linear Temporal Logic: Expressiveness and Model Checking. PhD thesis, Faculty of Informatics, Masaryk University, Brno, Czech Republic, 2004. |

[SU02] | Marcus Schaefer and Christopher Umans. Completeness in the Polynomial-Time hierarchy: A Compendium. SIGACT News 33(3):32-49. ACM Press, September 2002. |

[SU02] | Marcus Schaefer and Christopher Umans. Completeness in the Polynomial-Time hierarchy: Part II. SIGACT News 33(4):22-36. ACM Press, December 2002. |

[SVD01] | Jan Springintveld, Frits Vaandrager, and Pedro R. D'Argenio. Testing timed automata. Theoretical Computer Science 254(1-2):225-257. Elsevier, March 2001. |

[SVM+12] | Diego V. Simões De Sousa, Henrique Viana, Nicolas Markey, and Jose Antônio F. de Macêdo. Querying Trajectories through Model Checking based on Timed Automata. In SBBD'12, pages 33-40. Sociedade Brasileira de Computação, October 2012. |

[SVW85] | A. Prasad Sistla, Moshe Y. Vardi, and Pierre Wolper. The Complementation Problem for Büchi Automata, with Applications to Temporal Logic. In ICALP'85, Lecture Notes in Computer Science 194, pages 465-474. Springer-Verlag, July 1985. |

[SVW87] | A. Prasad Sistla, Moshe Y. Vardi, and Pierre Wolper. The Complementation Problem for Büchi Automata with Applications to Temporal Logics. Theoretical Computer Science 49:217-237. Elsevier, 1987. |

[SW10] | Chrstoffer Sloth and Rafael Wisniewski. Timed Game Abstraction of Control Systems. Technical Report 1012.5113, arXiv, December 2010. |

[SW13] | Chrstoffer Sloth and Rafael Wisniewski. Complete abstractions of dynamical systems by timed automata. Nonlinear Analysis: Hybrid Systems 7(1):80-100. February 2013. |

[SZH+09] | Mathijs Schuts, Yunshan Zhu, Faranak Heidarian, and Frits Vaandrager. Modelling Clock Synchronization in the Chess gMAC WSN Protocol. In QFM'09, Electronic Proceedings in Theoretical Computer Science 13, pages 41-54. November 2009. |