Search Results

Documents authored by Pratt-Hartmann, Ian

Document
DOI: 10.4230/LIPIcs.CPM.2024.25
Walking on Words

Authors: Ian Pratt-Hartmann

Published in: LIPIcs, Volume 296, 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)

Abstract
Any function f with domain {1, … , m} and co-domain {1, … , n} induces a natural map from words of length n to those of length m: the ith letter of the output word (1 ≤ i ≤ m) is given by the f(i)th letter of the input word. We study this map in the case where f is a surjection satisfying the condition |f(i+1)-f(i)| ≤ 1 for 1 ≤ i < m. Intuitively, we think of f as describing a "walk" on a word u, visiting every position, and yielding a word w as the sequence of letters encountered en route. If such an f exists, we say that u generates w. Call a word primitive if it is not generated by any word shorter than itself. We show that every word has, up to reversal, a unique primitive generator. Observing that, if a word contains a non-trivial palindrome, it can generate the same word via essentially different walks, we obtain conditions under which, for a chosen pair of walks f and g, those walks yield the same word when applied to a given primitive word. Although the original impulse for studying primitive generators comes from their application to decision procedures in logic, we end, by way of further motivation, with an analysis of the primitive generators for certain word sequences defined via morphisms.
Cite as

Ian Pratt-Hartmann. Walking on Words. In 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 296, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{pratthartmann:LIPIcs.CPM.2024.25,
  author =	{Pratt-Hartmann, Ian},
  title =	{{Walking on Words}},
  booktitle =	{35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-326-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{296},
  editor =	{Inenaga, Shunsuke and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2024.25},
  URN =		{urn:nbn:de:0030-drops-201352},
  doi =		{10.4230/LIPIcs.CPM.2024.25},
  annote =	{Keywords: word combinatorics, palindrome, Rauzy morphism}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2023.111
On the Limits of Decision: the Adjacent Fragment of First-Order Logic

Authors: Bartosz Bednarczyk, Daumantas Kojelis, and Ian Pratt-Hartmann

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We define the adjacent fragment AF of first-order logic, obtained by restricting the sequences of variables occurring as arguments in atomic formulas. The adjacent fragment generalizes (after a routine renaming) two-variable logic as well as the fluted fragment. We show that the adjacent fragment has the finite model property, and that its satisfiability problem is no harder than for the fluted fragment (and hence is Tower-complete). We further show that any relaxation of the adjacency condition on the allowed order of variables in argument sequences yields a logic whose satisfiability and finite satisfiability problems are undecidable. Finally, we study the effect of the adjacency requirement on the well-known guarded fragment (GF) of first-order logic. We show that the satisfiability problem for the guarded adjacent fragment (GA) remains 2ExpTime-hard, thus strengthening the known lower bound for GF.
Cite as

Bartosz Bednarczyk, Daumantas Kojelis, and Ian Pratt-Hartmann. On the Limits of Decision: the Adjacent Fragment of First-Order Logic. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 111:1-111:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bednarczyk_et_al:LIPIcs.ICALP.2023.111,
  author =	{Bednarczyk, Bartosz and Kojelis, Daumantas and Pratt-Hartmann, Ian},
  title =	{{On the Limits of Decision: the Adjacent Fragment of First-Order Logic}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{111:1--111:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.111},
  URN =		{urn:nbn:de:0030-drops-181632},
  doi =		{10.4230/LIPIcs.ICALP.2023.111},
  annote =	{Keywords: decidability, satisfiability, variable-ordered logics, complexity}
}
Document
DOI: 10.4230/LIPIcs.CSL.2023.32
Adding Transitivity and Counting to the Fluted Fragment

Authors: Ian Pratt-Hartmann and Lidia Tendera

Published in: LIPIcs, Volume 252, 31st EACSL Annual Conference on Computer Science Logic (CSL 2023)

Abstract
We study the impact of adding both counting quantifiers and a single transitive relation to the fluted fragment - a fragment of first-order logic originating in the work of W.V.O. Quine. The resulting formalism can be viewed as a multi-variable, non-guarded extension of certain systems of description logic featuring number restrictions and transitive roles, but lacking role-inverses. We establish the finite model property for our logic, and show that the satisfiability problem for its k-variable sub-fragment is in (k+1)-NExpTime. We also derive ExpSpace-hardness of the satisfiability problem for the two-variable, fluted fragment with one transitive relation (but without counting quantifiers), and prove that, when a second transitive relation is allowed, both the satisfiability and the finite satisfiability problems for the two-variable fluted fragment with counting quantifiers become undecidable.
Cite as

Ian Pratt-Hartmann and Lidia Tendera. Adding Transitivity and Counting to the Fluted Fragment. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 252, pp. 32:1-32:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{pratthartmann_et_al:LIPIcs.CSL.2023.32,
  author =	{Pratt-Hartmann, Ian and Tendera, Lidia},
  title =	{{Adding Transitivity and Counting to the Fluted Fragment}},
  booktitle =	{31st EACSL Annual Conference on Computer Science Logic (CSL 2023)},
  pages =	{32:1--32:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-264-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{252},
  editor =	{Klin, Bartek and Pimentel, Elaine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2023.32},
  URN =		{urn:nbn:de:0030-drops-174933},
  doi =		{10.4230/LIPIcs.CSL.2023.32},
  annote =	{Keywords: fluted logic, transitivity, counting, satisfiability, decidability, complexity}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2021.141
Fluted Logic with Counting

Authors: Ian Pratt-Hartmann

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
The fluted fragment is a fragment of first-order logic in which the order of quantification of variables coincides with the order in which those variables appear as arguments of predicates. It is known that the fluted fragment possesses the finite model property. In this paper, we extend the fluted fragment by the addition of counting quantifiers. We show that the resulting logic retains the finite model property, and that the satisfiability problem for its (m+1)-variable sub-fragment is in m-NExpTime for all positive m. We also consider the satisfiability and finite satisfiability problems for the extension of any of these fragments in which the fluting requirement applies only to sub-formulas having at least three free variables.
Cite as

Ian Pratt-Hartmann. Fluted Logic with Counting. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 141:1-141:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{pratthartmann:LIPIcs.ICALP.2021.141,
  author =	{Pratt-Hartmann, Ian},
  title =	{{Fluted Logic with Counting}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{141:1--141:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.141},
  URN =		{urn:nbn:de:0030-drops-142101},
  doi =		{10.4230/LIPIcs.ICALP.2021.141},
  annote =	{Keywords: Fluted fragment, counting quantifiers, satisfiability, complexity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.18
The Fluted Fragment with Transitivity

Authors: Ian Pratt-Hartmann and Lidia Tendera

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
We study the satisfiability problem for the fluted fragment extended with transitive relations. We show that the logic enjoys the finite model property when only one transitive relation is available. On the other hand we show that the satisfiability problem is undecidable already for the two-variable fragment of the logic in the presence of three transitive relations.
Cite as

Ian Pratt-Hartmann and Lidia Tendera. The Fluted Fragment with Transitivity. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{pratthartmann_et_al:LIPIcs.MFCS.2019.18,
  author =	{Pratt-Hartmann, Ian and Tendera, Lidia},
  title =	{{The Fluted Fragment with Transitivity}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.18},
  URN =		{urn:nbn:de:0030-drops-109626},
  doi =		{10.4230/LIPIcs.MFCS.2019.18},
  annote =	{Keywords: First-Order logic, Decidability, Satisfiability, Transitivity, Complexity}
}
Document
DOI: 10.4230/LIPIcs.CSL.2016.39
Quine's Fluted Fragment is Non-Elementary

Authors: Ian Pratt-Hartmann, Wieslaw Szwast, and Lidia Tendera

Published in: LIPIcs, Volume 62, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)

Abstract
We study the fluted fragment, a decidable fragment of first-order logic with an unbounded number of variables, originally identified by W.V. Quine. We show that the satisfiability problem for this fragment has non-elementary complexity, thus refuting an earlier published claim by W.C. Purdy that it is in NExpTime. More precisely, we consider, for all m greater than 1, the intersection of the fluted fragment and the m-variable fragment of first-order logic. We show that this sub-fragment forces (m/2)-tuply exponentially large models, and that its satisfiability problem is (m/2)-NExpTime-hard. We round off by using a corrected version of Purdy's construction to show that the m-variable fluted fragment has the m-tuply exponential model property, and that its satisfiability problem is in m-NExpTime.
Cite as

Ian Pratt-Hartmann, Wieslaw Szwast, and Lidia Tendera. Quine's Fluted Fragment is Non-Elementary. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 39:1-39:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{pratthartmann_et_al:LIPIcs.CSL.2016.39,
  author =	{Pratt-Hartmann, Ian and Szwast, Wieslaw and Tendera, Lidia},
  title =	{{Quine's Fluted Fragment is Non-Elementary}},
  booktitle =	{25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
  pages =	{39:1--39:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-022-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{62},
  editor =	{Talbot, Jean-Marc and Regnier, Laurent},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.39},
  URN =		{urn:nbn:de:0030-drops-65791},
  doi =		{10.4230/LIPIcs.CSL.2016.39},
  annote =	{Keywords: Quine, fluted fragment, Purdy, non-elementary, satisfiability, decidability}
}
Document
DOI: 10.4230/DagSemProc.05151.8
From TimeML to TPL

Authors: Ian Pratt-Hartmann

Published in: Dagstuhl Seminar Proceedings, Volume 5151, Annotating, Extracting and Reasoning about Time and Events (2005)

Abstract
This paper describes a subset of the temporal mark-up language TimeML, and explains its relation to various formalisms found in the literature on interval temporal logic. The subset of TimeML we describe can be viewed as an interval temporal logic with a tractable satisfiability problem, but very limited expressive power. Most crucially, that logic does not permit quantification over events. The contribution of this paper is to point out that, by choosing an appropriate interval temporal logic, it is possible to introduce quantification into representations of event-structure without sacrificing decidability.
Cite as

Ian Pratt-Hartmann. From TimeML to TPL. In Annotating, Extracting and Reasoning about Time and Events. Dagstuhl Seminar Proceedings, Volume 5151, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{pratthartmann:DagSemProc.05151.8,
  author =	{Pratt-Hartmann, Ian},
  title =	{{From TimeML to TPL}},
  booktitle =	{Annotating, Extracting and Reasoning about Time and Events},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5151},
  editor =	{Graham Katz and James Pustejovsky and Frank Schilder},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05151.8},
  URN =		{urn:nbn:de:0030-drops-3128},
  doi =		{10.4230/DagSemProc.05151.8},
  annote =	{Keywords: Information Extraction, Interval temporal logic}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact