The search session has expired. Please query the service again.
Displaying 1001 –
1020 of
2186
We study five extensions of the polymorphically typed lambda-calculus (system
F) by type constructs intended to model fixed-points of monotone
operators. Building on work by Geuvers
concerning the relation between term
rewrite systems for least pre-fixed-points and greatest post-fixed-points of
positive type schemes (i.e., non-nested positive inductive and coinductive
types) and so-called
retract types, we show that there are
reduction-preserving
embeddings even between systems of monotone (co)inductive...
In response to [3] and [4] we prove that the recognition of cover graphs of finite posets is an NP-hard problem.
We prove that the subsets of that are S-recognizable for all abstract numeration systems S are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional setting.
We prove that the subsets of that are S-recognizable for all abstract numeration systems S are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional setting.
Multigenerative grammar systems are based on cooperating context-free grammatical components that simultaneously generate their strings in a rule-controlled or nonterminal-controlled rewriting way, and after this simultaneous generation is completed, all the generated terminal strings are combined together by some common string operations, such as concatenation, and placed into the generated languages of these systems. The present paper proves that these systems are equivalent with the matrix grammars....
This paper discusses -island finite automata whose transition graphs can be expressed as -member sequences of islands , where there is a bridge leaving and entering for each . It concentrates its attention on even computation defined as any sequence of moves during which these automata make the same number of moves in each of the islands. Under the assumption that these automata work only in an evenly computational way, the paper proves its main result stating that -island finite automata...
A general definition of a quantum predicate and quantum labelled transition systems for finite quantum computation systems is presented. The notion of a quantum predicate as a positive operator-valued measure is developed. The main results of this paper are a theorem about the existence of generalised predicates for quantum programs defined as completely positive maps and a theorem about the existence of a GSOS format for quantum labelled transition systems. The first theorem is a slight generalisation...
In the XML standard, data are represented as unranked labeled
ordered trees. Regular unranked tree automata provide a useful
formalism for the validation of schemas enforcing regular structural
constraints on XML documents. However some concrete application
contexts need the expression of more general constraints than the
regular ones. In this paper we propose a new framework in which
context-free style structural constraints can be expressed and
validated. This framework is characterized by: (i)...
Currently displaying 1001 –
1020 of
2186