HyClt310s2008: Study Material


General

Logic - automaton connection

  • C. Elgot: Decision problems of finite automata and related arithmetics. Trans. Amer. Math. Soc. 98: 21-51 (1961)
  • J. Richard Büchi. Weak Second-Order Arithmetic and Finite Automata. Mathematical Logic Quarterly Volume 6, Issue 1-6 , Pages 66 - 92. 1960.
  • James Glenn and William Gasarch: Implementing WS1S via Finite Automata. WIA '96: Revised Papers from the First International Workshop on Implementing Automata. Lecture Notes in Computer Science 1260. Pages: 50--63. Springer. (1995)
  • Wolfgang Thomas: Languages, Automata, and Logic. Chapter in the Handbook of Formal Languages. Alternative version: Bericht 9607. Institut für Informatik und Praktische Mathematik der Christian-Albrechts-Universität zu Kiel. (1996) (SELECTED ARTICLE)
  • Nils Klarlund. 1997. Mona & Fido: The Logic-Automaton Connection in Practice. In Selected Papers from the11th International Workshop on Computer Science Logic. Lecture Notes In Computer Science. Vol. 1414. Pages: 311 - 326. Springer.
  • Nils Karlund. A theory of restrictions for logics and automata. In Proceedings of the 11th International Conference on Computer Aided Verification. LNCS 1633, pp. 406 - 417 (1999)
  • Klaus Reinhardt: The Complexity of Translating Logic to Finite Automata. Chapter 13 in E. Grädel et al. (Eds.): _Automata, Logics, and Infinite Games, LNCS 2500, pp. 231-238, Springer-Verlag Berlin Heidelberg. (2002)
  • Felix Klaedtke. Bounds on the Automata Size for Presburger Arithmetic. ACM Transactions on Computational Logic, Vol. 9, No. 2, Article 11, Publication date: March 2008.

On regular relations via MSO:

Descriptive complexity of PTIME and PH

  • T. Eiter, G. Gottlob and Y. Gurevitch: Existential Second-Order Logic over Strings. IFIG Research Report 9702, Institut für Informatik, Universität Giessen, 1997.
  • Ronald Fagin and Larry J. Stockmeyer and Moshe Y. Vardi: On Monadic NP vs. Monadic co-NP. Information and Computation 120(1):78-92 July (1995).

Descriptive complexity of FO[<] definable languages

  • R. Cohen and J. Brzozowski: Dot-depth of star-free events. J. Comput. Syst. Sci. 5:1-16 (1971)
  • Wolfgang Thomas: Classifying Regular Events in Symbolic Logic. J. C. S. Sci. 25(3): 360-376 (1982)

Finite Model Theory

  • Leonid Libkin: Elements of Finite Model Theory. Springer.

Named Disjunctions

  • John T. Maxwell III and Ronald M. Kaplan: A Method for Disjunctive Constraint Satisfaction. In Masaru Tomita (Ed.), _Current Issues in Parsing Technology, pp. 173-190. Kluwer Academic Publishers (1991)
  • Anssi Yli-Jyrä and K. Koskenniemi. 2004. Compiling contextual restrictions on strings into finite-state automata. FASTAR Days. Eindhoven. (SELECTED ARTICLE)

On regular relations from star-free definable sets

  • Michael Benedikt, Leonid Libkin, Thomas Schwentich and Luc Segoufin: A Model-Theoretic Approach to Regular String Relations. In Logic in Computer Science, 2001. Proceedings. 16th Annual IEEE Symposium on, vol., no., pp.431-440 (2001)
  • Måns Hulden. Regular expressions and predicate logic in finite-state language processing. FSMNLP 2008. (2008) (SELECTED ARTICLE)
  • Anssi Yli-Jyrä: Describing syntax with star-free expressions. In EACL 2003. 379-386. (2003)
  • Anssi Yli-Jyrä and K. Koskenniemi. 2004. Compiling contextual restrictions on strings into finite-state automata. FASTAR Days. Eindhoven. (SELECTED ARTICLE)
  • Anssi Yli-Jyrä and Kimmo Koskenniemi: Compiling Generalized Two-Level Rules and Grammars. FinTAL 2006: 174-185. (2006)
  • Anssi Yli-Jyrä: Applications of Diamonded Double Negation. In Finite-state methods and natural language processing. Thomas Hanneforth and Kay-Michael Würtzner. 6th International Workshop, FSMNLP 2007. Potsdam, Germany, September 14--16. Revised Papers. Universitätsverlag Potsdam. 2008a. (SELECTED ARTICLE)
  • Anssi Yli-Jyrä: Transducers from Parallel Replace Rules and Modes with Generalized Lenient Composition. In Finite-state methods and natural language processing. Thomas Hanneforth and Kay-Michael Würtzner. 6th International Workshop, FSMNLP 2007. Potsdam, Germany, September 14--16. Revised Papers. Universitätsverlag Potsdam. 2008b.

Modal Logic and other Logical Systems For Time Intervals

  • Moshe Y. Vardi and Pierre Wolper: An Automata-Theoretic Approach to Automatic Program Verification. (1985)
  • Pierre Wolper: Constructing Automata from Temporal Logic Formulas: A Tutorial.
  • Steven Bird and Patric Blackburn: A Logical Approach to Arabic Phonology. In EACL 1991, pp. 89-94. (1991)
  • Patrick Blackburn: Nominal tense logic. Notre Dame J. Formal Logic 34(1): 56-83 (1992)
  • Patrick Blackburn: Nominal Tense Logic and Other Sorted Intensional Frameworks. (1990)
  • Stéphane Demri: Sequent Calculi for Nominal Tense Logics: A Step Towards Mechanization?. (1999)
  • Stanford Encyclopedia of Philosophy: Hybrid Logic. (2008)
  • Balder ten Cate: Model Theory for Extended Modal Languages. Ph.D. thesis, Institute for Logic, Language and Computation, University of Amsterdam. (2004)

Logical systems for trees

  • Stephan Kepser: Using MONA for Querying Linguistic Treebanks. 2005.
  • Frank Neven: Automata Theory for XML researchers. SIGMOD Record (COLUMN: Database principles,_ 31(3):39-46, September 2002.
  • James Rogers: wMSO Theories as Grammar Formalisms. Elsevier Preprint. 2001

Logic, Graphs and Fixed Parameter Tractability:

  • Bruno Courcelle: Graph Structure and Monadic Second-order Logic: Language Theoretical Aspects....

Less used logic-automaton connections

  • Klaus U. Schulz and Dov M. Gabbay: Logic Finite Automata.
  • S. Eppstein: Word Processing in Groups.

AnssiYliJyra - 2008-10-31

Topic revision: r7 - 2008-12-08 - AnssiYliJyra
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback