BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Clemens Grabmayer

Clemens Grabmayer appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Logic in Computer ScienceProgramming LanguagesFormal Languages and Automata TheorySymbolic Computation

Catalog footprint

What is connected

13works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

13 published item(s)

preprint2021arXiv

Structure-Constrained Process Graphs for the Process Semantics of Regular Expressions

Milner (1984) introduced a process semantics for regular expressions as process graphs. Unlike for the language semantics, where every regular (that is, DFA-accepted) language is the interpretation of some regular expression, there are finite process graphs that are not bisimilar to the process interpretation of any regular expression. For reasoning about graphs that are expressible by regular expressions modulo bisimilarity it is desirable to have structural representations of process graphs in the image of the interpretation. For '1-free' regular expressions, their process interpretations satisfy the structural property LEE (loop existence and elimination). But this is not in general the case for all regular expressions, as we show by examples. Yet as a remedy, we describe the possibility to recover the property LEE for a close variant of the process interpretation. For this purpose we refine the process semantics of regular expressions to yield process graphs with 1-transitions, similar to silent moves for finite-state automata.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Complete Proof System for 1-Free Regular Expressions Modulo Bisimilarity

Robin Milner (1984) gave a sound proof system for bisimilarity of regular expressions interpreted as processes: Basic Process Algebra with unary Kleene star iteration, deadlock 0, successful termination 1, and a fixed-point rule. He asked whether this system is complete. Despite intensive research over the last 35 years, the problem is still open. This paper gives a partial positive answer to Milner's problem. We prove that the adaptation of Milner's system over the subclass of regular expressions that arises by dropping the constant 1, and by changing to binary Kleene star iteration is complete. The crucial tool we use is a graph structure property that guarantees expressibility of a process graph by a regular expression, and is preserved by going over from a process graph to its bisimulation collapse.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Nested Term Graphs (Work In Progress)

We report on work in progress on 'nested term graphs' for formalizing higher-order terms (e.g. finite or infinite lambda-terms), including those expressing recursion (e.g. terms in the lambda-calculus with letrec). The idea is to represent the nested scope structure of a higher-order term by a nested structure of term graphs. Based on a signature that is partitioned into atomic and nested function symbols, we define nested term graphs both in a functional representation, as tree-like recursive graph specifications that associate nested symbols with usual term graphs, and in a structural representation, as enriched term graph structures. These definitions induce corresponding notions of bisimulation between nested term graphs. Our main result states that nested term graphs can be implemented faithfully by first-order term graphs. keywords: higher-order term graphs, context-free grammars, cyclic lambda-terms, higher-order rewrite systems

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Regularity Preserving but not Reflecting Encodings

Encodings, that is, injective functions from words to words, have been studied extensively in several settings. In computability theory the notion of encoding is crucial for defining computability on arbitrary domains, as well as for comparing the power of models of computation. In language theory much attention has been devoted to regularity preserving functions. A natural question arising in these contexts is: Is there a bijective encoding such that its image function preserves regularity of languages, but its pre-image function does not? Our main result answers this question in the affirmative: For every countable class C of languages there exists a bijective encoding f such that for every language L in C its image f[L] is regular. Our construction of such encodings has several noteworthy consequences. Firstly, anomalies arise when models of computation are compared with respect to a known concept of implementation that is based on encodings which are not required to be computable: Every countable decision model can be implemented, in this sense, by finite-state automata, even via bijective encodings. Hence deterministic finite-state automata would be equally powerful as Turing machine deciders. A second consequence concerns the recognizability of sets of natural numbers via number representations and finite automata. A set of numbers is said to be recognizable with respect to a representation if an automaton accepts the language of representations. Our result entails that there is one number representation with respect to which every recursive set is recognizable.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Degree of Squares is an Atom (Extended Version)

We answer an open question in the theory of degrees of infinite sequences with respect to transducibility by finite-state transducers. An initial study of this partial order of degrees was carried out in (Endrullis, Hendriks, Klop, 2011), but many basic questions remain unanswered. One of the central questions concerns the existence of atom degrees, other than the degree of the `identity sequence' 1 0^0 1 0^1 1 0^2 1 0^3 .... A degree is called an `atom' if below it there is only the bottom degree 0, which consists of the ultimately periodic sequences. We show that also the degree of the `squares sequence' 1 0^0 1 0^1 1 0^4 1 0^9 1 0^{16} ... is an atom. As the main tool for this result we characterise the transducts of `spiralling' sequences and their degrees. We use this to show that every transduct of a `polynomial sequence' either is in 0 or can be transduced back to a polynomial sequence for a polynomial of the same order.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Infinitary Term Rewriting for Weakly Orthogonal Systems: Properties and Counterexamples

We present some contributions to the theory of infinitary rewriting for weakly orthogonal term rewrite systems, in which critical pairs may occur provided they are trivial. We show that the infinitary unique normal form property fails by an example of a weakly orthogonal TRS with two collapsing rules. By translating this example, we show that this property also fails for the infinitary lambda-beta-eta-calculus. As positive results we obtain the following: Infinitary confluence, and hence the infinitary unique normal forms property, holds for weakly orthogonal TRSs that do not contain collapsing rules. To this end we refine the compression lemma. Furthermore, we establish the triangle and diamond properties for infinitary multi-steps (complete developments) in weakly orthogonal TRSs, by refining an earlier cluster-analysis for the finite case.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Maximal Sharing in the Lambda Calculus with letrec

Increasing sharing in programs is desirable to compactify the code, and to avoid duplication of reduction work at run-time, thereby speeding up execution. We show how a maximal degree of sharing can be obtained for programs expressed as terms in the lambda calculus with letrec. We introduce a notion of `maximal compactness' for lambda-letrec-terms among all terms with the same infinite unfolding. Instead of defined purely syntactically, this notion is based on a graph semantics. lambda-letrec-terms are interpreted as first-order term graphs so that unfolding equivalence between terms is preserved and reflected through bisimilarity of the term graph interpretations. Compactness of the term graphs can then be compared via functional bisimulation. We describe practical and efficient methods for the following two problems: transforming a lambda-letrec-term into a maximally compact form; and deciding whether two lambda-letrec-terms are unfolding-equivalent. The transformation of a lambda-letrec-term $L$ into maximally compact form $L_0$ proceeds in three steps: (i) translate L into its term graph $G = [[ L ]]$; (ii) compute the maximally shared form of $G$ as its bisimulation collapse $G_0$; (iii) read back a lambda-letrec-term $L_0$ from the term graph $G_0$ with the property $[[ L_0 ]] = G_0$. This guarantees that $L_0$ and $L$ have the same unfolding, and that $L_0$ exhibits maximal sharing. The procedure for deciding whether two given lambda-letrec-terms $L_1$ and $L_2$ are unfolding-equivalent computes their term graph interpretations $[[ L_1 ]]$ and $[[ L_2 ]]$, and checks whether these term graphs are bisimilar. For illustration, we also provide a readily usable implementation.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Expressibility in the Lambda Calculus with Letrec

We investigate the relationship between finite terms in lambda-letrec, the lambda calculus with letrec, and the infinite lambda terms they express. As there are easy examples of lambda-terms that, intuitively, are not unfoldings of terms in lambda-letrec, we consider the question: How can those infinite lambda terms be characterised that are lamda-letrec-expressible in the sense that they can be obtained as infinite unfoldings of terms in lambda-letrec? For 'observing' infinite lambda-terms through repeated 'experiments' carried out at the head of the term we introduce two rewrite systems (with rewrite relations) -reg-> and -reg+-> that decompose the term, and produce 'generated subterms' in two notions. Thereby the sort of the step can be observed as well as its target, a generated subterm. In both systems there are four sorts of decomposition steps: -lambda-> steps (decomposing a lambda-abstraction), -@0> and -@1> steps (decomposing an application into its function and argument), and respectively, -del-> steps (delimiting the scope of an abstraction, for -reg->), and -S-> (delimiting of scopes, for -reg+->). These steps take place on infinite lambda-terms furnished with a leading prefix of abstractions for gathering previously encountered lambda-abstractions and keeping the generated subterms closed. We call an infinite lambda-term 'regular'/'strongly regular' if its set of -reg-> -reachable / -reg-> -reachable generated subterms is finite. Furthermore, we analyse the binding structure of lambda-terms with the concept of 'binding-capturing chain'. Using these concepts, we answer the question above by providing two characterisations of lambda-letrec-expressibility. For all infinite lambda-terms M, the following statements are equivalent: (i) M is lambda-letrec-expressible; (ii) M is strongly regular; (iii) M is regular, and it only has finite binding-capturing chains.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Expressibility in the Lambda Calculus with mu

We address a problem connected to the unfolding semantics of functional programming languages: give a useful characterization of those infinite lambda-terms that are lambda_{letrec}-expressible in the sense that they arise as infinite unfoldings of terms in lambda_{letrec}, the lambda-calculus with letrec. We provide two characterizations, using concepts we introduce for infinite lambda-terms: regularity, strong regularity, and binding-capturing chains. It turns out that lambda_{letrec}-expressible infinite lambda-terms form a proper subclass of the regular infinite lambda-terms. In this paper we establish these characterizations only for expressibility in lambda_{mu}, the lambda-calculus with explicit mu-recursion. We show that for all infinite lambda-terms T the following are equivalent: (i): T is lambda_{mu}-expressible; (ii): T is strongly regular; (iii): T is regular, and it only has finite binding-capturing chains. We define regularity and strong regularity for infinite lambda-terms as two different generalizations of regularity for infinite first-order terms: as the existence of only finitely many subterms that are defined as the reducts of two rewrite relations for decomposing lambda-terms. These rewrite relations act on infinite lambda-terms furnished with a marked prefix of abstractions for collecting decomposed lambda-abstractions and keeping the terms closed under decomposition. They differ in how vacuous abstractions in the prefix are removed. This report accompanies the article with the same title for the proceedings of the conference RTA 2013, and mainly differs from that by providing the proof of the characterization of lambda_{mu}-expressibility with binding-capturing chains.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Term Graph Representations for Cyclic Lambda-Terms

We study various representations for cyclic lambda-terms as higher-order or as first-order term graphs. We focus on the relation between `lambda-higher-order term graphs' (lambda-ho-term-graphs), which are first-order term graphs endowed with a well-behaved scope function, and their representations as `lambda-term-graphs', which are plain first-order term graphs with scope-delimiter vertices that meet certain scoping requirements. Specifically we tackle the question: Which class of first-order term graphs admits a faithful embedding of lambda-ho-term-graphs in the sense that: (i) the homomorphism-based sharing-order on lambda-ho-term-graphs is preserved and reflected, and (ii) the image of the embedding corresponds closely to a natural class (of lambda-term-graphs) that is closed under homomorphism? We systematically examine whether a number of classes of lambda-term-graphs have this property, and we find a particular class of lambda-term-graphs that satisfies this criterion. Term graphs of this class are built from application, abstraction, variable, and scope-delimiter vertices, and have the characteristic feature that the latter two kinds of vertices have back-links to the corresponding abstraction. This result puts a handle on the concept of subterm sharing for higher-order term graphs, both theoretically and algorithmically: We obtain an easily implementable method for obtaining the maximally shared form of lambda-ho-term-graphs. Also, we open up the possibility to pull back properties from first-order term graphs to lambda-ho-term-graphs. In fact we prove this for the property of the sharing-order successors of a given term graph to be a complete lattice with respect to the sharing order. This report extends the paper with the same title (http://arxiv.org/abs/1302.6338v1) in the proceedings of the workshop TERMGRAPH 2013.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Term Graph Representations for Cyclic Lambda-Terms

We study various representations for cyclic lambda-terms as higher-order or as first-order term graphs. We focus on the relation between 'lambda-higher-order term graphs' (lambda-ho-term-graphs), which are first-order term graphs endowed with a well-behaved scope function, and their representations as 'lambda-term-graphs', which are plain first-order term graphs with scope-delimiter vertices that meet certain scoping requirements. Specifically we tackle the question: Which class of first-order term graphs admits a faithful embedding of lambda-ho-term-graphs in the sense that (i) the homomorphism-based sharing-order on lambda-ho-term-graphs is preserved and reflected, and (ii) the image of the embedding corresponds closely to a natural class (of lambda-term-graphs) that is closed under homomorphism? We systematically examine whether a number of classes of lambda-term-graphs have this property, and we find a particular class of lambda-term-graphs that satisfies this criterion. Term graphs of this class are built from application, abstraction, variable, and scope-delimiter vertices, and have the characteristic feature that the latter two kinds of vertices have back-links to the corresponding abstraction. This result puts a handle on the concept of subterm sharing for higher-order term graphs, both theoretically and algorithmically: We obtain an easily implementable method for obtaining the maximally shared form of lambda-ho-term-graphs. Furthermore, we open up the possibility to pull back properties from first-order term graphs to lambda-ho-term-graphs, properties such as the complete lattice structure of bisimulation equivalence classes with respect to the sharing order.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Automatic Sequences and Zip-Specifications

We consider infinite sequences of symbols, also known as streams, and the decidability question for equality of streams defined in a restricted format. This restricted format consists of prefixing a symbol at the head of a stream, of the stream function `zip', and recursion variables. Here `zip' interleaves the elements of two streams in alternating order, starting with the first stream. For example, the Thue-Morse sequence is obtained by the `zip-specification' {M = 0 : X, X = 1 : zip(X,Y), Y = 0 : zip(Y,X)}. Our analysis of such systems employs both term rewriting and coalgebraic techniques. We establish decidability for these zip-specifications, employing bisimilarity of observation graphs based on a suitably chosen cobasis. The importance of zip-specifications resides in their intimate connection with automatic sequences. We establish a new and simple characterization of automatic sequences. Thus we obtain for the binary zip that a stream is 2-automatic iff its observation graph using the cobasis (hd,even,odd) is finite. The generalization to zip-k specifications and their relation to k-automaticity is straightforward. In fact, zip-specifications can be perceived as a term rewriting syntax for automatic sequences. Our study of zip-specifications is placed in an even wider perspective by employing the observation graphs in a dynamic logic setting, leading to an alternative characterization of automatic sequences. We further obtain a natural extension of the class of automatic sequences, obtained by `zip-mix' specifications that use zips of different arities in one specification. We also show that equivalence is undecidable for a simple extension of the zip-mix format with projections like even and odd. However, it remains open whether zip-mix specifications have a decidable equivalence problem.

0 citations0 reviewsNo code linkedOpen access