The Experts below are selected from a list of 321 Experts worldwide ranked by ideXlab platform
Zoltán Ésik - One of the best experts on this subject based on the ideXlab platform.
-
Axiomatizing the Equational Theory of regular tree languages
The Journal of Logic and Algebraic Programming, 2010Co-Authors: Zoltán ÉsikAbstract:AbstractWe show that a finite set of equation schemes together with the least fixed point rule gives a complete axiomatization of the valid identities of regular tree languages. This result is a generalization of Kozen’s axiomatization of the Equational Theory of regular word languages
-
The Equational Theory of regular words
Information and Computation, 2005Co-Authors: Stephen L. Bloom, Zoltán ÉsikAbstract:AbstractCourcelle introduced the study of regular words, i.e., words isomorphic to frontiers of regular trees. Heilbrunner showed that a nonempty word is regular iff it can be generated from the singletons by the operations of concatenation, omega power, omega-op power, and the infinite family of shuffle operations. We prove that the algebra of nonempty regular words on the set A, equipped with these operations, is freely generated by A in a variety which is axiomatizable by an infinite collection of some natural equations. We also show that this variety has no finite Equational basis and that its Equational Theory is decidable in polynomial time
-
nonfinite axiomatizability of the Equational Theory of shuffle
Acta Informatica, 1998Co-Authors: Zoltán Ésik, Michael BertolAbstract:We consider language structures ${\bf L}_\Sigma = (P_\Sigma,\cdot,\otimes,+,1,0)$ , where $P_\Sigma$ consists of all subsets of the free monoid $\Sigma^*$ ; the binary operations $\cdot$ , $\otimes$ and $+$ are concatenation, shuffle product and union, respectively, and where the constant 0 is the empty set and the constant 1 is the singleton set containing the empty word. We show that the variety Lang generated by the structures ${\bf L}_\Sigma$ has no finite axiomatization. In fact we establish a stronger result: The variety Lang has no finite axiomatization over the variety of ordered algebras ${\bf Lg}_\leq$ generated by the structures $(P_\Sigma,\cdot,\otimes,1,\subseteq)$ , where $\subseteq$ denotes set inclusion.
-
axiomatizing the Equational Theory of regular tree languages extended anstract
Symposium on Theoretical Aspects of Computer Science, 1998Co-Authors: Zoltán ÉsikAbstract:We show that a finite set of equation schemes together with the least fixed point rule gives a complete axiomatization of the valid identities of regular tree languages. This result is a generalization of Kozen's axiomatization of the Equational Theory of regular word languages.
-
nonfinite axiomatizability of the Equational Theory of shuffle
International Colloquium on Automata Languages and Programming, 1995Co-Authors: Zoltán Ésik, Michael BertolAbstract:We consider language structures B Σ = (P Σ , ·, ⊗, +, 1,0), where P Σ consists of all subsets of the free monoid σ*; the binary operations ·, ⊗ and + are concatenation, shuffle product and union, respectively, and where the constant 0 is the empty set and the constant 1 is the singleton set containing the empty word. We show that the variety Lang generated by the structures L Σ has no finite axiomatization.
Igor Dolinka - One of the best experts on this subject based on the ideXlab platform.
-
The multiplicative fragment of the Yanov Equational Theory
Theoretical Computer Science, 2003Co-Authors: Igor DolinkaAbstract:AbstractWe give a finite Equational axiomatization for +-free identities of (regular) languages which contain the empty word. The axioms for the whole Equational Theory of such languages were given by Yanov
-
A Variety with Undecidable Equational Theory and Solvable Word Problem
International Journal of Algebra and Computation, 1998Co-Authors: Siniša Crvenković, Igor DolinkaAbstract:In this paper, we exhibit an example of a variety with only one binary operation having recursive base, undecidable Equational Theory and solvable word problem.
Steve Zdancewic - One of the best experts on this subject based on the ideXlab platform.
-
an Equational Theory for weak bisimulation via generalized parameterized coinduction
Certified Programs and Proofs, 2020Co-Authors: Yannick Zakowski, Chungkil Hur, Steve ZdancewicAbstract:Coinductive reasoning about infinitary structures such as streams is widely applicable. However, practical frameworks for developing coinductive proofs and finding reasoning principles that help structure such proofs remain a challenge, especially in the context of machine-checked formalization. This paper gives a novel presentation of an Equational Theory for reasoning about structures up to weak bisimulation. The Theory is both compositional, making it suitable for defining general-purpose lemmas, and also incremental, meaning that the bisimulation can be created interactively. To prove the Theory’s soundness, this paper also introduces generalized parameterized coinduction, which addresses expressivity problems of earlier works and provides a practical framework for coinductive reasoning. The paper presents the resulting Equational Theory for streams, but the technique applies to other structures too. All of the results in this paper have been proved in Coq, and the generalized parameterized coinduction framework is available as a Coq library.
-
A HoTT Quantum Equational Theory (Extended Version).
arXiv: Programming Languages, 2019Co-Authors: Jennifer Paykin, Steve ZdancewicAbstract:This paper presents an Equational Theory for the QRAM model of quantum computation, formulated as an embedded language inside of homotopy type Theory. The embedded language approach is highly expressive, and reflects the style of state-of-the art quantum languages like Quipper and QWIRE. The embedding takes advantage of features of homotopy type Theory to encode unitary transformations as higher inductive paths, simplifying the presentation of an Equational Theory. We prove that this Equational Theory is sound and complete with respect to established models of quantum computation.
-
a formal Equational Theory for call by push value
Interactive Theorem Proving, 2018Co-Authors: Christine Rizkallah, Dmitri Garbuzov, Steve ZdancewicAbstract:Establishing that two programs are contextually equivalent is hard, yet essential for reasoning about semantics preserving program transformations such as compiler optimizations. We adapt Lassen’s normal form bisimulations technique to establish the soundness of Equational theories for both an untyped call-by-value \(\lambda \)-calculus and a variant of Levy’s call-by-push-value language. We demonstrate that our Equational Theory significantly simplifies the verification of optimizations.
Michael Bertol - One of the best experts on this subject based on the ideXlab platform.
-
nonfinite axiomatizability of the Equational Theory of shuffle
Acta Informatica, 1998Co-Authors: Zoltán Ésik, Michael BertolAbstract:We consider language structures ${\bf L}_\Sigma = (P_\Sigma,\cdot,\otimes,+,1,0)$ , where $P_\Sigma$ consists of all subsets of the free monoid $\Sigma^*$ ; the binary operations $\cdot$ , $\otimes$ and $+$ are concatenation, shuffle product and union, respectively, and where the constant 0 is the empty set and the constant 1 is the singleton set containing the empty word. We show that the variety Lang generated by the structures ${\bf L}_\Sigma$ has no finite axiomatization. In fact we establish a stronger result: The variety Lang has no finite axiomatization over the variety of ordered algebras ${\bf Lg}_\leq$ generated by the structures $(P_\Sigma,\cdot,\otimes,1,\subseteq)$ , where $\subseteq$ denotes set inclusion.
-
nonfinite axiomatizability of the Equational Theory of shuffle
International Colloquium on Automata Languages and Programming, 1995Co-Authors: Zoltán Ésik, Michael BertolAbstract:We consider language structures B Σ = (P Σ , ·, ⊗, +, 1,0), where P Σ consists of all subsets of the free monoid σ*; the binary operations ·, ⊗ and + are concatenation, shuffle product and union, respectively, and where the constant 0 is the empty set and the constant 1 is the singleton set containing the empty word. We show that the variety Lang generated by the structures L Σ has no finite axiomatization.
Anna Ingólfsdóttir - One of the best experts on this subject based on the ideXlab platform.
-
the Equational Theory of weak complete simulation semantics over bccsp
Conference on Current Trends in Theory and Practice of Informatics, 2012Co-Authors: Luca Aceto, David De Frutosescrig, Carlos Gregoriorodriguez, Anna IngólfsdóttirAbstract:This paper presents a complete account of positive and negative results on the finite axiomatizability of weak complete simulation semantics over the language BCCSP. We offer finite (un)conditional ground-complete axiomatizations for the weak complete simulation precongruence. In sharp contrast to this positive result, we prove that, in the presence of at least one observable action, the (in)Equational Theory of the weak complete simulation precongruence over BCCSP does not have a finite (in)Equational basis. In fact, the set of (in)equations in at most one variable that hold in weak complete simulation semantics over BCCSP does not have an (in)Equational basis of ‘bounded depth', let alone a finite one.
-
The Equational Theory of prebisimilarity over basic CCS with divergence
Information Processing Letters, 2008Co-Authors: Luca Aceto, Silvio Capobianco, Anna Ingólfsdóttir, Bas LuttikAbstract:This paper studies the Equational Theory of prebisimilarity, a bisimulation-based preorder introduced by Hennessy and Milner in the early 1980s, over basic CCS with the divergent process @W. It is well known that prebisimilarity affords a finite ground-complete axiomatization over this language; this study proves that this ground-complete axiomatization is also complete in the presence of an infinite set of actions. Moreover, in sharp contrast to this positive result, it is shown that prebisimilarity is not finitely based over basic CCS with the divergent process @W when the set of actions is finite and nonempty.
-
impossibility results for the Equational Theory of timed ccs
Conference on Algebra and Coalgebra in Computer Science, 2007Co-Authors: Luca Aceto, Anna Ingólfsdóttir, Mohammad Reza MousaviAbstract:We study the Equational Theory of Timed CCS as proposed by Wang Yi in CONCUR'90. Common to Wang Yi's paper, we particularly focus on a class of linearly-ordered time domains exemplified by the positive real or rational numbers. We show that, even when the set of basic actions is a singleton, there are parallel Timed CCS processes that do not have any sequential equivalent and thus improve on the Gap Theorem for Timed CCS presented by Godskesen and Larsen in FSTTCS'92. Furthermore, we show that timed bisimilarity is not finitely based both for single-sorted and two-sorted presentations of Timed CCS. We further strengthen this result by showing that, unlike in some other process algebras, adding the untimed or the timed left-merge operator to the syntax and semantics of Timed CCS does not solve the axiomatizability problem.
-
on a question of a salomaa the Equational Theory of regular expression
Theoretical Computer Science, 1998Co-Authors: Luca Aceto, Wan Fokkink, Anna IngólfsdóttirAbstract:Salomaa (1969, p. 143) asked whether the Equational Theory of regular expressions over a singleton alphabet has a finite Equational base. In this paper, we provide a negative answer to this long-standing question. The proof of our main result rests upon a model-theoretic argument. For every finite collection of equations, that are sound in the algebra of regular expressions over a singleton alphabet, we build a model in which some valid regular equation fails. The construction of the model mimics the one used by Conway (1971, p. 105) in his proof of a result, originally due to Redko, to the effect that infinitely many equations are needed to axiomatize equality of regular expressions. Our analysis of the model, however, needs to be more refined than the one provided by Conway (1971).
-
on a question of arto salomaa the Equational Theory of regular expressions over a singleton alphabet is not finitely based
BRICS Report Series, 1996Co-Authors: Luca Aceto, Wan Fokkink, Anna IngólfsdóttirAbstract:Salomaa ((1969) Theory of Automata, page 143) asked whether the Equational Theory of regular expressions over a singleton alphabet has a finite Equational base. In this paper, we provide a negative answer to this long standing question. The proof of our main result rests upon a model-theoretic argument. For every finite collection of equations, that are sound in the algebra of regular expressions over a singleton alphabet, we build a model in which some valid regular equation fails. The construction of the model mimics the one used by Conway ((1971) Regular Algebra and Finite Machines, page 105) in his proof of a result, originally due to Redko, to the effect that infinitely many equations are needed to axiomatize equality of regular expressions. Our analysis of the model, however, needs to be more refined than the one provided by Conway ibidem. AMS Subject Classification (1991): 08A70, 03C05, 68Q45, 68Q68, 68Q70. CR Subject Classification (1991): D.3.1, F.1.1, F.4.1. Keywords and Phrases: Regular expressions, Equational logic, complete axiomatizations.
