some publications

K. Etessami, C. Papadimitriou, A. Rubinstein, M. Yannakakis, Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria. Preprint: ArXiv:1909.03210, 2019. Conference version to appear in Proceedings of 11th Innovations in Theoretical Computer Science conference (ITCS'20), 2020.

K. Etessami, E. Martinov, A. Stewart, and M. Yannakakis, "Reachability for Branching Concurrent Stochastic Games". Preprint: ArXiv:1806.03907, 2018. Conference version to appear in Proc. of 46th Int. Coll. on Automata, Languages, and Programming (ICALP'19).

K. Etessami, A. Stewart, and M. Yannakakis, "Greatest Fixed Points of Probabilistic Min/Max Polynomial Equations, and Reachability for Branching Markov Decision Processes". Conference version in Proc. of 42nd Int. Coll. on Automata, Languages and Programming (ICALP'15). Preprint: ArXiv:1502.05533, 2015. Journal version appeared in Information and Computation, volume 261, pages 355-382, 2018.

K. Etessami, "The complexity of computing a (quasi-)perfect equilibrium for an n-player extensive form game of perfect recall" (submitted), 2014. Preprint: ArXiv:1408.1233 . To appear in the journal Games and Economic Behavior , 2019.

K. Etessami, K. A. Hansen, P. B. Miltersen, T. B. Sorensen, "The complexity of approximating a trembling hand perfect equilibrium of a multi-player game in strategic form". Conference version in Proc. of 7th Int. Symp. on Algorithmic Game Theory (SAGT'14), 2014. Preprint: ArXiv:1408.1017.

( Survey (DRAFT): ) K. Etessami "Analysis of Probabilistic Processes and Automata Theory". DRAFT of Chapter in forthcoming Handbook of Automata Theory, editor Jean-Eric Pin, European Mathmatical Society publishing (EMS), to appear in 2015 (??).

K. Etessami, A. Stewart, and M. Yannakakis, "A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing". ACM Transactions on Computation Theory, volume 6 (2), 2014. Preprint: ArXiv:1302.6411, 2013.

K. Etessami, A. Stewart, and M. Yannakakis, "Stochastic Context-Free Grammars, Regular Languages, and Newton's Method", Conference version in ICALP'2013, Preprint: ArXiv:1302.6411, 2013.

A. Stewart, K. Etessami, and M. Yannakakis, "Upper bounds for Newton's method on monotone polynomial systems, and P-time model checking of probabilistic one-counter automata", in Journal of the ACM, volume 62(4), 30 pages, 2015. (Conference version appeared in CAV'2013.) Preprint: arXiv:1302:3741, 2013.

K. Etessami, A. Stewart, and M. Yannakakis, "Polynomial-time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations", manuscript 2012 . Conference version in Proc. of 39th Int. Coll. on Automata, Languages and Programming (ICALP'12), 2012. Preprint: ArXiv:1202.4798. Journal version to appear in Mathematics of Operations Research, 2019.

K. Etessami, A. Stewart, and M. Yannakakis, "Polynomial-time Algorithms for Multi-type Branching Processes and Stochastic Context-Free Grammars", manuscript 2011. Conference version in Proc. 44th ACM Symp. on Theory of Computing (STOC'12), 2012. Preprint: ArXiv:1201.2374.
A part of the work in this conference paper has appeared in journal form under the title "A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes.", in the SIAM Journal on Computing, 45(6), pp. 1515-1553, 2017.

T. Brazdil, V. Brozek, K. Etessami, and T. Kucera, "Approximating the Termination value of One-counter MDPs and Stochastic Games", Journal version in Information and Computation , volume 222, pp. 121-138, 2013. full preprint (of the journal version) available here. Conference version in Proc. of 38th Int. Coll. on Automata, Languages and Programming (ICALP'11), pages 332-343, 2011.

T. Brazdil, V. Brozek, and K. Etessami, One-Counter Stochastic Games, full preprint (20 pages), 2010. Conference version appeared in Proc. of Ann. Conf. on Foundations of Software Technology and theoretical computer science (FSTTCS'10), pages 108-119, 2010.

T. Brazdil, V. Brozek, K. Etessami, A. Kucera, D. Wojtczak, One-Counter Markov Decision Processes, Preprint: arXiv:0904.2511, 2009. In Proc. 21st ACM-SIAM Symp. on Discrete Algorithms (SODA'2010), 2010.

K. Etessami and P. Godefroid, An Abort-Aware Model of Transactional Programming, appeared in Proc. of 10th Int. Conf. on Verification, Model Checking, and Abstract Interpretation (VMCAI'09), 2009. (Also a Microsoft Research Tech Report: MSR-TR-2008-159, 2008. A short Position Paper based on this work appeared earlier at the (EC)^2 Workshop, 2008.)

K. Etessami, D. Wojtczak, and M. Yannakakis, Quasi-Birth-Death Processes, Tree-Like QBDs, Probabilistic 1-Counter Automata, and Pushdown Systems. Performance Evaluation, volume 67(9), pages 837-857, 2010. Conference version appeared in 5th Int. Conf. on Quantitative Evaluation of Systems (QEST'08), 2008.

K. Etessami and M. Yannakakis, On the complexity of Nash equilibria and other fixed points, SIAM Journal on Computing, Vol. 39(6), pp. 2531--2597, 2010. The earlier conference version appeared in 48th IEEE Symp. on Foundations of Computer Science (FOCS), 2007.

K. Etessami, D. Wojtczak, and M. Yannakakis, Recursive Stochastic Games with Positive Rewards, Tech Report, U. of Edinburgh, EDI-INF-RR-1224, 2007. Conference version appeared in 35th Int. Coll. on Automata, Languages and Programming (ICALP'08), 2008.

R. Alur, M. Arenas, P. Barcelo, K. Etessami, N. Immerman, and L. Libkin, First-Order and Temporal Logics for Nested Words , in 22nd IEEE Symposium on Logic in Computer Science (LICS), 2007. Here is the Journal version, which appeared in Logical Methods in Computer Science (LMCS), volume 4(4): 2008.

K. Etessami, M. Kwiatkowska, M. Y. Vardi, and M. Yannakakis, Multi-Objective Model Checking of Markov Decision Processes, in 13th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'07), 2007. Here is the Journal version, in Logical Methods in Computer Science (LMCS), volume 4(4), 2008.

D. Wojtczak and K. Etessami PReMo: an analyzer for probabilistic recursive models, (short tool paper) in 13th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'07), 2007. Here is a longer version with some more experimental results in the appendix.

K. Etessami and M. Yannakakis, Recursive Concurrent Stochastic Games, in 33nd Int. Coll. on Automata, Languages and Programming (ICALP'06), 2006. Here is the Journal version, which appeared in Logical Methods in Computer Science (LMCS), volume 4(4): 2008.

K. Etessami and M. Yannakakis, Efficient Qualitative Analysis of classes of Recursive Markov Decision Processes and Simple Stochastic Games, in 23rd Symp. on Theoretical Aspects of Computer Science (STACS'06), 2006.
See the full journal paper, to appear in Journal of the ACM (70 pages), 2015. The journal paper combines the results of both our ICALP'05 paper (see below) and this STACS'06 paper.

M. Yannakakis and K. Etessami, Checking LTL properties of Recursive Markov Chains, in 2nd Int. Conf. on Quantitative Evaluation of Systems (QEST'05), 2005.
The full version of this paper (60 pages) titled Model Checking of Recursive Probabilistic Systems, appears in the journal ACM Transactions on Computational Logic, available electronically here, together with an electronic appendix available here (2012). The full journal version combines the results of both our TACAS'05 paper (see below) and this QEST'05 paper on the same topic.

K. Etessami and M. Yannakakis, Recursive Markov Decision Processes and Recursive Stochastic Games, to appear in Journal of the ACM, 70 pages, 2015. Conference version appeared in 32nd Int. Coll. on Automata, Languages and Programming (ICALP'05), 2005.
The journal version (to appear in JACM, 2015) combines the results of both this ICALP'05 paper and our STACS'06 paper (see above).

K. Etessami and M. Yannakakis, Algorithmic Verification of Recursive Probabilistic State Machines. in 11th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'05), 2005.
The full version of this paper (60 pages) titled Model Checking of Recursive Probabilistic Systems, appears in the journal ACM Trans. on Computational Logic (2012), (available electronically here), together with an electronic appendix available here. The journal version combines the results of both this TACAS'05 paper and our QEST'05 paper (see above) on the same topic.

R. Alur, S. Chaudhuri, K. Etessami, P. Madhusudan, On-the-fly Reachability and Cycle Detection for Recursive State Machines, in 11th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'05), 2005.

J. Esparza and K. Etessami, Verifying Probabilistic Procedural Programs. In FSTTCS'04, December, 2004.(Invited early survey, for talk by Esparza. Briefly surveys our first paper [Etessami-Yannakakis,STACS'05] on Recursive Markov Chains, and also surveys Esparza, Kucera, et. al.'s work [LICS'04,STACS'05] on probabilistic Pushdown Systems.)

K. Etessami and M. Yannakakis, Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations. Journal of the Association for Computing Machinery (JACM) volume 56(1): January, 2009.
Here's the short conference version which appeared in 22nd Int. Symp. on Theoretical Aspects of Computer Science (STACS'05), 2005.

K. Etessami and A. Lochbihler, The Computational Complexity of Evolutionarily Stable Strategies. in Int. Journal of Game Theory, vol. 37 (1): 93--113, 2008. An earlier version was made available as a ECCC tech report TR04-055, 2004.

R. Alur, K. Etessami, and P. Madhusudan, A Temporal Logic of Nested Calls and Returns, In 10th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'04), 2004.

K. Etessami, Analysis of Recursive Game Graphs using Dataflow Equations In Proc. of 5th Int. Conf. on Verification, Model Checking, and Abstract Interpretation (VCMAI'04) , 2004.

R. Alur, S. Chaudhuri, K. Etessami, S. Guha, and M. Yannakakis. Compression of Partially Ordered Strings In Proc. of CONCUR'2003, Springer LNCS 2761, 2003.

K. Etessami. A hierarchy of polynomial-time computable simulations for automata. In Proc. of CONCUR'2002, Springer LNCS 2421, pages 131-144, 2002.

K. Etessami, Th. Wilke, and R. Schuller. Fair simulation relations, parity games, and state space reduction for Büchi automata. SIAM Journal on Computing, 34(5): 1159--1175, 2005.
Conference version appeared in Proc. of 28th Int. Col. on Automata, Languages, and Programming (ICALP'2001), Springer LNCS 2076, pages 694-707, 2001.

R. Alur, M. Benedikt, K. Etessami, P. Godefroid, T. Reps, and M. Yannakakis. Analysis of Recursive State Machines. in ACM Trans. on Programming Languages and Systems, 27(4): 786-818, 2005.
Conference version: R. Alur, K. Etessami, M. Yannakakis, Analysis of Recursive State Machines, In Proc. of 13th Conf. on Computer-Aided Verification (CAV'2001) , Springer LNCS 2102, pages 207-220, 2001.
(Journal paper joined with independent work of M. Benedikt, P. Godefroid, and T. Reps).

R. Alur, K. Etessami, and M. Yannakakis. Realizability and verification of MSC graphs. In Proc. of 28th Int. Col. on Automata, Languages, and Programming (ICALP'2001) . Full journal version appears Theoretical Computer Science, 2005.

K. Etessami and M. Yannakakis. From rule-based to automata-based testing. In Proc. of 20th IFIP Int. Conf. on Formal Description Techniques/Protocol Specification, Testing and Verification (FORTE/PSTV'2000), 2000.

K. Etessami. A note on a question of Peled and Wilke regarding stutter-invariant LTL, Information Processing Letters , vol. 75 (6), pp. 261-263, 2000.

K. Etessami and G. Holzmann. Optimizing Büchi automata, in Proc. of 11th Int. Conf. on Concurrency Theory (CONCUR'2000) , pp. 153-167, 2000.

R. Alur, K. Etessami, and M. Yannakakis. Inference of message sequence charts, Journal version appeared in IEEE Transactions on Software Engineering, 2003 , volume 29(7), pp. 623-633. Due to space limitations in the journal, here is the Full Version, more complete than the journal paper . Conference version appeared in Proc. of 22nd Int. Conf. on Software Engineering (ICSE'2000) , pp. 304-313, 2000.

R. Alur, K. Etessami, S. LaTorre, and D. Peled, Parametric temporal logic for model measuring , in ACM Transactions on Computational Logic , vol. 2 (3), pp. 388-407, 2001. Conference version appeared in Proc. of 26th Int. Coll. on . Automata, Languages, and Programming (ICALP'99), pp. 159-168, 1999.

K. Etessami, Stutter-invariant languages, omega-automata, and temporal logic, in Proc. of 11th Int. Conf. on Computer-Aided Verification (CAV'99) , pp. 236-248, 1999.

K. Etessami, Dynamic tree isomorphism via first-order updates to a relational database, in Proc. of 17th ACM Symp. on Principles of Database Systems (PODS'98) , 1998, pp. 235-243.

K. Etessami, M. Y. Vardi, and Th. Wilke First-order logic with two variables and unary temporal logic, Information and Computation , volume 179(2), pp. 279-295, 2002. Conference version appeared in Proc. of 12th IEEE Symp. on Logic in Computer Science (LICS'97) , pp. 228-235, 1997.

K. Etessami and Th. Wilke. An Until Hierarchy and Other Applications of an Ehrenfeucht-Fraisse Game for Temporal Logic, Information and Computation , volume 160(1/2), pp. 88-108, 2000. Conference version appeared as "An Until Hierarchy for Temporal Logic" in Proc. of 11th IEEE Symp. on Logic in Computer Science (LICS'96) , pp. 108-117, 1996.

K. Etessami. Counting quantifiers, successor relations, and logarithmic space, Journal of Computer and System Sciences , volume 54(3), pp. 400-411, 1997. Conference version appeared in Proc. of 10th IEEE Structure in Complexity Theory Conference (Structures'95) , pp. 1-11, 1995.

K. Etessami and N. Immerman, Tree canonization and transitive closure, Information and Computation , volume 157(1/2), pp. 2-24, 2000. Conference version appeared in Proc. of 10th IEEE Symp. on Logic in Computer Science (LICS'95) , pp. 331-341, 1995.

K. Etessami and N. Immerman, Reachability and the power of local ordering, in Theoretical Computer Science , volume 149, pp. 227-260, 1995. Conference version appeared in 11th Symposium on Theoretical Aspects of Computer Science (STACS'94) , pp. 123-135, 1994.