Daniel S. Hono Ii
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Daniel S. Hono Ii has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Paliath Narendran
University at Albany-SUNY
2 shared publications - Andrew Pulver
Department of Computer Science University at Albany Albany 12222 NY
1 shared publication - Kimberly A. Cornell
University at Albany
1 shared publication - Rafael Veras
University at Albany
1 shared publication - Zümrüt Akçam1 shared publication
Latest Publications
- Open Access
- 28 May 2025
- Published by University Libraries, University at Albany, State University of New York
Some problems from higher-order unification
Unification deals with the solving of equations over terms. Higher-order unification extends
- 28 May 2025
- Published by University Libraries, University at Albany, State University of New York
Open AccessSome problems from higher-order unification
Unification deals with the solving of equations over terms. Higher-order unification extends
- Open Access
On Problems Dual to Unification: The String-Rewriting Case
In this paper, we investigate problems which are dual to the unification problem, namely the Fixed Point (FP) problem, Common Term (CT) problem and the Common Equation (CE) problem for string rewriting systems. Our main motivation is computing fixed points in systems, such as loop invariants in programming languages. We show that the fixed point (FP) problem is reducible to the common term problem. Our new results are: (i) the fixed point problem is undecidable for finite convergent string rewriting systems whereas it is decidable in polynomial time for finite, convergent and dwindling string rewriting systems, (ii) the common term problem is undecidable for the class of dwindling string rewriting systems, and (iii) for the class of finite, monadic and convergent systems, the common equation problem is decidable in polynomial time but for the class of dwindling string rewriting systems, common equation problem is undecidable.
Open AccessOn Problems Dual to Unification: The String-Rewriting Case
In this paper, we investigate problems which are dual to the unification problem, namely the Fixed Point (FP) problem, Common Term (CT) problem and the Common Equation (CE) problem for string rewriting systems. Our main motivation is computing fixed points in systems, such as loop invariants in programming languages. We show that the fixed point (FP) problem is reducible to the common term problem. Our new results are: (i) the fixed point problem is undecidable for finite convergent string rewriting systems whereas it is decidable in polynomial time for finite, convergent and dwindling string rewriting systems, (ii) the common term problem is undecidable for the class of dwindling string rewriting systems, and (iii) for the class of finite, monadic and convergent systems, the common equation problem is decidable in polynomial time but for the class of dwindling string rewriting systems, common equation problem is undecidable.
- Open Access
Lynch-Morawska Systems on Strings
We investigate properties of convergent and forward-closed string rewriting systems in the context of the syntactic criteria introduced in \cite{LynchMorawska} by Christopher Lynch and Barbara Morawska (we call these $LM$-Systems). Since a string rewriting system can be viewed as a term-rewriting system over a signature of purely monadic function symbols, we adapt their definition to the string rewriting case. We prove that the subterm-collapse problem for convergent and forward-closed string rewriting systems is effectively solvable. Therefore, there exists a decision procedure that verifies if such a system is an $LM$-System. We use the same construction to prove that the \emph{cap problem} from the field of cryptographic protocol analysis, which is undecidable for general $LM$-systems, is decidable when restricted to the string rewriting case.
Open AccessLynch-Morawska Systems on Strings
We investigate properties of convergent and forward-closed string rewriting systems in the context of the syntactic criteria introduced in \cite{LynchMorawska} by Christopher Lynch and Barbara Morawska (we call these $LM$-Systems). Since a string rewriting system can be viewed as a term-rewriting system over a signature of purely monadic function symbols, we adapt their definition to the string rewriting case. We prove that the subterm-collapse problem for convergent and forward-closed string rewriting systems is effectively solvable. Therefore, there exists a decision procedure that verifies if such a system is an $LM$-System. We use the same construction to prove that the \emph{cap problem} from the field of cryptographic protocol analysis, which is undecidable for general $LM$-systems, is decidable when restricted to the string rewriting case.