Arrow Research search

Author name cluster

Albert R. Meyer

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

18 papers
2 author rows

Possible papers

18

TCS Journal 1996 Journal Article

Deciding true concurrency equivalences on safe, finite nets

  • Lalita Jategaonkar
  • Albert R. Meyer

We show that the pomset-trace equivalence problem for 1-safe, finite Petri nets is decidable; in fact it is complete for expspace. We also show that history-preserving bisimulation between such nets is complete for dexptime. Our methods also yield tight complexity bounds for several other “true concurrency” and interleaving equivalences. The results are independent of the presence of hidden transitions.

Details DOI

TCS Journal 1992 Journal Article

Experimenting with process equivalence

  • Bard Bloom
  • Albert R. Meyer

Distinctions between concurrent processes based on observable outcomes of computational experiments are examined. The equivalence determined by a general class of experiments involving duplication of processes can be characterized by a notion of ready simulation resembling, but strictly coarser than, Milner's bisimulation equivalence.

Details DOI

I&C Journal 1990 Journal Article

The semantics of second-order lambda calculus

  • Kim B. Bruce
  • Albert R. Meyer
  • John C. Mitchell

In the second-order (polymorphic) typed lambda calculus, lambda abstraction over type variables leads to terms denoting polymorphic functions. Straightforward cardinality considerations show that a naive set-theoretic interpretation of the calculus is impossible. We give two definitions of semantic models for this language and prove them equivalent. Our syntactical “environment model” definition and a more algebraic “combinatory model” definition for the polymorphic calculus correspond to analogous model definitions for untyped lambda calculus. Soundness and completeness theorems are proved using the environment model definition. We verify that some specific interpretations of the calculus proposed in the literature indeed yield models in our sense.

Details DOI

TCS Journal 1982 Journal Article

Expressing program looping in regular dynamic logic

  • Albert R. Meyer
  • Karl Winklmann

‘Looping’ of nondeterministic while-programs is shown to be expressible in Regular First Order Dynamic Logic with or without array assignment instructions in the programs. The expressive power of quantifier-free Dynamic Logic increases when nondeterminism is introduced in the programs that are part of formulae of Dynamic Logic. Allowing assignments of random values to variables also increases expressive power.

Details DOI

STOC Conference 1980 Conference Paper

Definability in Dynamic Logic

  • Albert R. Meyer
  • Rohit Parikh

We study the expressive power of various versions of Dynamic Logic and compare them with each other as well as with standard languages in the logical literature. One version of Dynamic Logic is equivalent to the infinitary logic L CK ω 1 ω , but regular Dynamic Logic is strictly less expressive. In particular, the ordinals ω ω and ω ω .2 are indistinguishable by formulas of regular Dynamic Logic.

Details

TCS Journal 1980 Journal Article

On time-space classes and their relation to the theory of real addition

  • Anna R. Bruss
  • Albert R. Meyer

A new lower bound on the computational complexity of the theory of real addition and several related theories is established: any decision procedure for these theories requires either space 2 εn or nondeterministic time 2 εn 2 for some constant ε0 and infinitely many n. The proof is based on the families of languages TISP(T(n), S(n)) which can be recognized simultaneously in time T(n) and S(n) and the conditions under which they form a hierarchy.

Details DOI

STOC Conference 1978 Conference Paper

Coping with Errors in Binary Search Procedures (Preliminary Report)

  • Ronald L. Rivest
  • Albert R. Meyer
  • Daniel J. Kleitman
  • Karl Winklmann
  • Joel Spencer

We consider the problem of identifying an unknown value xε{1,2,...,n} using only comparisons of x to constants when as many as E of 'the comparisons may receive erroneous answers. For a continuous analogue of this problem we show that there is a unique strategy that is optimal in the worst case. This strategy for the continuous problem is then shown to yield a strategy for the original discrete problem that uses log 2 n+E.log 2 log 2 n+O(E.log 2 E) comparisons in the worst case. This number is shown to be optimal even if arbitrary “Yes-No” questions are allowed. We show that a modified version of this search problem with errors is equivalent to the problem of finding the minimal root of a set of increasing functions. The modified version is then also shown to be of complexity log 2 n+E.log 2 log 2 n+0(E.log 2 E).

Details

STOC Conference 1978 Conference Paper

On Time-Space Classes and Their Relation to the Theory of Real Addition

  • Anni R. Bruss
  • Albert R. Meyer

A new lower bound on the computational complexity of the theory of real addition and several related theories is established: any decision procedure for these theories requires either space 2 εn or nondeterministic time 2 εn 2 for some constant ε > O and infinitely many n. The proof is based on the families of languages TISP(T(n),S(n)) which can be recognized simultaneously in time T(n) and space S(n) and the conditions under which they form a hierarchy.

Details

STOC Conference 1973 Conference Paper

Word Problems Requiring Exponential Time: Preliminary Report

  • Larry J. Stockmeyer
  • Albert R. Meyer

The equivalence problem for Kleene's regular expressions has several effective solutions, all of which are computationally inefficient. In [1], we showed that this inefficiency is an inherent property of the problem by showing that the problem of membership in any arbitrary context-sensitive language was easily reducible to the equivalence problem for regular expressions. We also showed that with a squaring abbreviation ( writing (E) 2 for E×E) the equivalence problem for expressions required computing space exponential in the size of the expressions. In this paper we consider a number of similar decidable word problems from automata theory and logic whose inherent computational complexity can be precisely characterized in terms of time or space requirements on deterministic or nondeterministic Turing machines. The definitions of the word problems and a table summarizing their complexity appears in the next section. More detailed comments and an outline of some of the proofs follows in the remaining sections. Complete proofs will appear in the forthcoming papers [9, 10, 13]. In the final section we describe some open problems.

Details

STOC Conference 1969 Conference Paper

Classes of Computable Functions Defined by Bounds on Computation: Preliminary Report

  • Edward M. McCreight
  • Albert R. Meyer

The structure of the functions computable in time or space bounded by t is investigated for recursive functions t. The t-computable classes are shown to be closed under increasing recursively enumerable unions; as a corollary the primitive recursive functions are shown to equal the t-computable functions for a certain recursive t. Any countable partial order can be isomorphically embedded in the family of t-computable classes partially ordered by set inclusion. For any recursive t, there is a recursive t' which is (approximately) equal to an actual running time such that the t-computable functions equal the t'-computable functions.

Details
v2026.09.13