DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2010.493

First-Order Logic with Reachability Predicates on Infinite Systems

Authors: Stefan Schulz

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Abstract

This paper focuses on first-order logic (FO) extended by reachability predicates such that the expressiveness and hence decidability properties lie between FO and monadic second-order logic (MSO): in FO(R) one can demand that a node is reachably from another by some sequence of edges, whereas in FO(Reg) a regular set of allowed edge sequences can be given additionally. We study FO(Reg) logic in infinite grid-like structures which are important in verification. The decidability of logics between FO and MSO on those simple structures turns out to be sensitive to various parameters. Furthermore we introduce a transformation for infinite graphs called set-based unfolding which is based on an idea of Lohrey and Ondrusch. It allows to transfer the decidability of MSO to FO(Reg) onto the class of transformed structures. Finally we extend regular ground tree rewriting with a skeleton tree. We show that graphs specified in this way coincide with those expressible by vertex replacement and product operators. This allows to extend decidability results of Colcombet for FO(R) to those graphs.

Cite as

Stefan Schulz. First-Order Logic with Reachability Predicates on Infinite Systems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 493-504, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{schulz:LIPIcs.FSTTCS.2010.493,
  author =	{Schulz, Stefan},
  title =	{{First-Order Logic with Reachability Predicates on Infinite Systems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{493--504},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.493},
  URN =		{urn:nbn:de:0030-drops-28896},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.493},
  annote =	{Keywords: First-Order Logic, Reachability, Infinite Grid, Structure Transformati on, Unfolding, Ground Tree Rewriting, Vertex Replacement with Product}
}

Document

DOI: 10.4230/DagSemProc.08131.9

Named Entity or Entity Name?

Authors: Stefan Schulz

Published in: Dagstuhl Seminar Proceedings, Volume 8131, Ontologies and Text Mining for Life Sciences : Current Status and Future Perspectives (2008)

Abstract

The expression "named entity" is very fuzzy and its definitions partly contradictory. Semantic subtleties involving the words "entity", "name" and "term" are largely ignored. Based on formal ontology a more principled typology is introduced.

Cite as

Stefan Schulz. Named Entity or Entity Name?. In Ontologies and Text Mining for Life Sciences : Current Status and Future Perspectives. Dagstuhl Seminar Proceedings, Volume 8131, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{schulz:DagSemProc.08131.9,
  author =	{Schulz, Stefan},
  title =	{{Named Entity or Entity Name?}},
  booktitle =	{Ontologies and Text Mining for Life Sciences : Current Status and Future Perspectives},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8131},
  editor =	{Michael Ashburner and Ulf Leser and Dietrich Rebholz-Schuhmann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08131.9},
  URN =		{urn:nbn:de:0030-drops-15214},
  doi =		{10.4230/DagSemProc.08131.9},
  annote =	{Keywords: Ontology, Named Entity Recognition}
}

Search Results

Documents authored by Schulz, Stefan

First-Order Logic with Reachability Predicates on Infinite Systems

Abstract

Cite as

Named Entity or Entity Name?

Abstract

Cite as

Thanks for your feedback!

Could not send message